[LeetCode] Hard - 149 Max Points on a Line

▶149 - Max Points on a Line

▶문제

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.

 

▶예제

Input: points = [[1,1],[2,2],[3,3]]
Output: 3

 

 

Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4

 

 

728x90

▶풀이

단순히 모든 점들을 확인해보는 방식을 사용했다.

시간 복잡도가 O(n^2)가 나오는 방식이라서 시간초과가 날까 봐 걱정했지만 통과가 되었다.

 

점들의 기울기 등을 dictionary에 저장하고, 같은 값이 나오면 1 증가시켰다.

그리고 max값을 찾아서 저장해두고 return을 할 때 1을 더해서 return 했다.

 

1을 더한 이유는, 값을 저장할 때, 시작이 되는 값은 저장을 하지 않기 때문에 마지막에 1을 더해주는 것이다.

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        def gcd(x, y):
            if y == 0:
                return x
            else:
                return gcd(y, x % y)
    

        if len(points) == 1:
            return 1

        answer = 0
        for i in range(len(points)):
            dic = defaultdict(int)

            for j in range(i + 1, len(points)):
                dx = points[i][0] - points[j][0]
                dy = points[i][1] - points[j][1]
                if dx == 0:
                    dic[(0, points[i][1])] += 1
                elif dy == 0:
                    dic[(points[i][0], 0)] += 1
                else:
                    d = gcd(dx, dy)
                    dic[(dx//d, dy//d)] += 1

            for v in dic.values():
                answer = max(answer, v)

        return answer + 1

dx, dy의 gcd를 구해서 나눠주고, 그 값들을 dictionary에 저장해두려고 했다.

내장 함수인 gcd를 써도, 내가 구현한 gcd를 써도 다 한두 개에서 실패가 나왔다.

그래서 구글링을 해보고 나온 방식을 사용했더니 정답이 나왔다.

이 부분에 대해서는 공부를 더 해야 할 것 같다.