149. Max Points on a Line

[zeikar]

Problem link

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

Problem Summary

같은 직선에 있는 점의 최대 개수를 구하는 문제.

Solution

인풋 범위가 300개로 매우 작아서 그냥 다 돌려보면 된다. 심지어 x, y 범위도 작아서 (-10000 ~ 10000) 단순 기울기로만 카운트를 해주면 된다.
단, x, y 범위가 크다면 부동소수점 오차로 인해 gcd를 이용해서 기울기가 같은 점을 더해줘야 한다.

Source Code

from typing import List


class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        ans = 1

        for i in range(len(points)):
            x1, y1 = points[i]

            gradients = dict({0: 0})
            for j in range(i + 1, len(points)):
                x2, y2 = points[j]

                g = (y2 - y1) / (x2 - x1) if x2 != x1 else 1e9
                gradients[g] = gradients.get(g, 0) + 1

            ans = max(ans, max(gradients.values()) + 1)

        return ans