leet code - 149. Max Points on a Line (hard, math)

 

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.

 

Example 1:

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

Example 2:

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

 

Constraints:

• 1 <= points.length <= 300
• points[i].length == 2
• -104 <= xi, yi <= 104
• All the points are unique.

 

 

 

points.length = 300 으로 모든 점 쌍에 대해 기울기를 계산할 수 있다. bruteforce. O(n^2)

 

한점을 기준으로 나머지 한 점과의 기울기를 구한다. 그리고 딕셔너리를 활용해 이 기울기의 갯수를 세어 Max 를 업데이트 한다.

외부포문으로 기준점을 구하고, 내부 포문에서는 기준점을 제외하고 체크하는 방식으로 체크한다.

이는 각 포문마다 딕셔너를 초기화하지만, 그럼에도 불구하고 각 직선. (기울기와 지나는 점이 동일 하다면)은 이미 체크되었다고 생각하기 떄문이다.

음양의 벡터 문제를 해결하기 위해 sort 를사용한다.
부동소수점 문제를 위해 gcd를 도입할 수도 있다.(파이썬 에서는 필요없을만큼 정확한 부동소수점 오차를 가지고 있다),

 

class Solution:
    def maxPoints(self, points: list[list[int]]) -> int:
        points.sort()
        slope, M = defaultdict(int), 0

        for i, (x1, y1) in enumerate(points):
            slope.clear()

            for x2, y2 in points[i + 1:]:
                dx, dy = x2 - x1, y2 - y1

                if dx == 0:
                    m = 'inf' 
                else:
                    m = dy / dx                 
                
                slope[m] += 1
                if slope[m] > M: M = slope[m]
    
        return M + 1