[LeetCode 문제풀이] 149. Max Points on a Line

https://leetcode.com/problems/max-points-on-a-line/

Max Points on a Line - LeetCode

 

평면상의 점 위치가 임의의 갯수 만큼 주어지고 해당 점들을 관통하는 직선을 그어서 이을 수 있는 점의 최대 갯수를 구하는 문제이다. 거의 한달은 푼 것 같다. 로직은 단순한데 코너케이스가 너무 많이 발생했다.

 

씨특키를 썼기 때문에 잘 짠 코드가 아님에도 불구하고 시간 점수는 잘 받은 것 같다.

 

단순한 것 같은데 생각보다 잘 안풀렸다.

 

이 문제를 풀면서 겪었던 코너 케이스들은 다음과 같다. 

 

1. 점 위치 자체가 중복되는 경우

-> 단순히 기울기만 비교하는 코드를 짜면 x증가량과 y증가량이 둘 다 0인 경우를 같은 선에 포함되지 않는 것으로 간주하는 경우가 있다.

 

2. 기울기가 0 또는 무한인 경우.

-> x증가량 또는 y증가량이 0인 경우이다. 이 경우는 일반적인 기울기와는 다르게 절편을 구하여 비교하고 따로 갯수를 구해서 비교해야한다.

 

int maxPoints(int** points, int pointsSize, int* pointsColSize){
    if(pointsSize < 3) {
        return pointsSize;
    }
    int i, j, k;
    int x, y;
    int sx, sy;
    int mx, my;
    int max = 0;    
    int imax = -1;
    int * cnt = malloc(sizeof(int) * pointsSize);
    int ** garr = malloc(sizeof(int*) * pointsSize);    
    
    for(i=0;i<pointsSize;i++) {
        for(j=i+1;j<pointsSize;j++) {
            if(points[i][0] > points[j][0]) {
                int * t = points[i];
                points[i] = points[j];
                points[j] = t;
            }                   
        }
    }
    int sign = 0;
    for(i=0;i<pointsSize;i++) {
        for(k=0;k<pointsSize;k++) {
            garr[k] = malloc(sizeof(int) * 2);
        }
        x = points[i][0];
        y = points[i][1];     
        cnt[i] = 1; //원래 점 하나
        sign = 0;
        for(j=i+1;j<pointsSize;j++) {
            sx = points[j][0];
            sy = points[j][1];                            
            mx = sx - x;
            my = sy - y;             
            
            if(mx == 0 && my == 0) {                 
                cnt[i]++;
                garr[j] = 0;
                continue;
            }
            else if(mx == 0) {
                sign = 1;
                garr[j][0] = 0;
                garr[j][1] = y;
            }    
            else if(my == 0) {
                sign = 1;
                garr[j][0] = x;
                garr[j][1] = 0;
            }
            else {
                sign = 1; 
                int a = mx;
                int b = my;                 
                while(a != 0) {
                    int t = b % a;                    
                    b = a;
                    a = t;
                }   
                mx /= b;
                my /= b;              
                garr[j][0] = mx;
                garr[j][1] = my;                
            }                                                  
        }      
        
        int count = 0;
        int countg = 0;
        int counts = 0;
        
        imax = 0;
        
        for(j=i+1;j<pointsSize;j++) 
        {
            if(garr[j] == 0) continue;
            count = 0;  
            counts= 0;
            countg= 0;
            for(k=j;k<pointsSize;k++) {
                if(garr[k] == 0) continue;
                if(garr[j][0] == garr[k][0] && garr[j][1] == garr[k][1])  {
                    count++;
                }
                if(garr[k][0] == 0 && garr[k][1] == garr[j][1]) {
                    counts++;
                }
                if(garr[k][1] == 0 && garr[k][0] == garr[j][0]) {
                    countg++;
                }
            }
            if(imax < count) imax = count;
            if(imax < counts) {                
                imax = counts;
            }
            if(imax < countg) {
                imax = countg;
            }
        }
        cnt[i] += imax;
        if(cnt[i] > max) {
            max = cnt[i];
        }
    }    
    return max;
}