149. Max Points on a Line

149. Max Points on a Line

 

https://youtu.be/Bb9lOXUOnFw?si=srijUp6iwLeL2_n5

 

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        # 1. for each pt determin if it lies on the logest line
        # 2. count all pts with same slop
        # 3. update result with max

        res = 1 # 최소 포인트 개수가 1개 이므로, 1개는 게런티 가능해서, 
        for i in range(len(points)): 
            p1 = points[i]

            # 해쉬 맵
            count = defaultdict(int)
            for j in range(i+1, len(points)):
                p2 = points[j]
                
                if p2[0] == p1[0]:
                    slop = float("inf")
                else:
                    slop = (p2[1]-p1[1]) / (p2[0]-p1[0])

                count[slop] += 1

                """
                # 여기에서 1을 더하는 이유는, 현재점 개수도 더해야 되서..
                count[slop] = 2라면, 
                    현재 p1에서 시작하여 기울기가 slop인 직선 위에 
                        2개의 다른 점(p2) 이 있다는 뜻 임
                따라서, +1을 추가하여 현재 점(p1)까지 포함된 직선 위의 모든 점의 개수를 계산.
                """
                res = max(res, count[slop]+1) 

        return res