leetcode 149, Max Points on a Line

문제 설명

x와 y의 좌표가 주어질 때, 선으로 만들 수 있는 최대한의 점 개수를 구하는 문제다. 간단한 수학 문제인 줄 알았지만, 실은 더 복잡했던 문제.

점과 점의 atan2 값을 구해가지고 만일 그 값이 같다면 이는 한 직선에 있다는 의미이므로 해당 값의 점의 수에다가 1을 더한다. 만일 해당 값이 새 값이라면 1을 넣는다.
그리고 최대값을 찾아서 리턴하면 된다.

문제 풀이

0. 변수들
   0-1. n, 좌표의 개수
   0-2. HashMap, atan2의 값을 key로 두고 해당 atan2의 개수를 세는 값(atan2가 같다는 것은 한 직선에 있음을 의미한다.)이 value인 HashMap.
   0-3. max, 한 직선에 있는 최대 점 개수
1. 먼저 좌표의 개수를 구해서 n에 넣는다. 그리고 만일 n이 1이라 좌표가 한 개이면 1을 반환한다.
2. 최대 값을 일단 2개(좌표가 1개인 경우는 1을 위에서 리턴했다)로 두고 각 좌표를 하나씩 기준으로 반복문을 돌린다.
   2-1. HashMap을 새로 정의하고 2중 반복문으로 내부 값을 돌리는데 만일 i가 j와 같지 않다면 merge(key, value, 갱신함수)를 이용해 값을 업데이트한다. 두 좌표의 atan2 값을 구해서 key 값에 넣는다. 만일 map에 해당 key가 없다면 1을 넣는다. 만일 값이 있다면 Integer::sum을 이용해서 해당 값에다가 1을 더해준다(조금 더 정확하게 말하자면 key에 값이 있다면 해당 값을 다시 구해서 넣어준다는 의미).
   merge -> https://exponential-e.tistory.com/76
3. 2차 반복문이 끝나면 map에 있는 최대 값과 현재 max를 비교해서 더 큰 값을 max에 넣어준다.
4. max를 반환한다.

코드

class Solution {
    public int maxPoints(int[][] points) {
        int n = points.length;

        if(n == 1){
            return 1;
        }

        int max = 2;
        for(int i=0; i<n; i++){
            Map<Double, Integer> map = new HashMap<>();
            for(int j=0; j<n; j++){
                if(i != j){
                    //key, value, remappingFunction
                    //((v1, v2) -> v2 : v1이 기존이고 v2가 새 값일 때 기존의 값을 사용한다는 것)       
                    map.merge(Math.atan2(points[j][1] - points[i][1],
                    	points[j][0] - points[i][0]), 1, Integer::sum);
                }
            }
            max = Math.max(max,  Collections.max(map.values()) + 1);
        }

        return max;
    }

}

링크

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