[Geometry 문제] LEETCODE.49. Max Points on a Line

문제풀이

이번 문제는 선분의 기울기를 활용하는 문제이다. 선분은 두 점만 정해지면 기울기가 정해진다는 특성에 기반하여 주어진 점들 중에서 같은 기울기를 가지는 선분들 중 가장 많은 개수의 점을 찾도록 처리하면 된다.

이를 위해 각 점 쌍의 기울기를 계산하고, 기울기별로 갯수를 계산한다.
점 쌍을 구하기 위해서 우선 Points 중 Pivot을 전체로 탐색하고 해당 Pivot과 대칭되는 Point는 Pivot 이후에 존재하는 Point를 대상으로 하여 기울기를 계산한다.
이 과정을 반복하여 가장 많은 점을 가진 선분의 개수를 찾도록 처리하면 간단히 해결할 수 있다.

코드

from collections import defaultdict
class Solution:
    def getslope(self,a,b):
        x1,y1= a[0],a[1]
        x2,y2= b[0],b[1]
        if x1==x2:
            slope = "vertical"
        elif y1==y2:
            slope = "horizontal"
        else:
            slope = (y2-y1)/(x2-x1)
        
        return slope
    
    def maxPoints(self, points: List[List[int]]) -> int:
        n = len(points)
        ans=0
        candidates=defaultdict(int)
        for i in range(n):            
            for j in range(i+1,n):
                candidates[self.getslope(points[i],points[j])]+=1
           # print(candidates,ans)
            if len(candidates)>0:
                ans=max(ans,max(candidates.values())) 
            candidates=defaultdict(int)       
       
        return ans+1
        
        

Lookback

1. Hard 문제라기보다 다분히 수학적인 문제로 판단된다.
2. 22년 쯤 이 문제를 접했을땐 어떤 것부터 해야할지 어떤 알고리즘을 알아야 할지 등을 고민해서 결국 풀지 못하였는데 꾸준히 하다보니 적절한 해결방안을 도출할 수 있어서 재미있었다.