leetcode hard : Max Points on a Line

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

Max Points on a Line - LeetCode

 

수상한점 : 점 개수가 적다 -> 노가다로 풀 수 있을 가능성 up

 

나는 이걸 생각해봤다.

효율성이고 뭐고 다 제쳐두고

어떤 점들이 같은 선상에 있다는걸 어떻게 알수있지? 라는 질문을 먼저 던져보았다.

답은 기울기다.

동일선상에 있는 점들은 임의의 두 점을 찍어서 y값 차이 / x값 차이 를 계산했을때 모두 같은 값이 나와야 된다.

그럼 모든 점들에 대해서 '다른 점들과 선을 그어서 동일선상에 있는 점 개수 세어보기'를 하면 될거같다.

같은 선상에 있는 점 개수 세는건 hash table로 word count하듯이 key를 기울기로 놓고 count하면 될것이다.

 

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        answer = 0
        INF = 10**9

        for i in range(len(points)):
            slopedict = defaultdict(int)
            maxpoints = 0

            for j in range(len(points)):
                if i != j:
                    xdiff = points[i][0] - points[j][0]
                    ydiff = points[i][1] - points[j][1]
                    slope = INF if xdiff == 0 else ydiff/xdiff
                    slopedict[slope] += 1
                    maxpoints = max(maxpoints, slopedict[slope])
            
            answer = max(answer, maxpoints + 1) # 자기 자신 count로 +1

        return answer

세심하게 divide by zero 예외도 생각한 모습 (뿌듯) ㅋㅋㅋㅋㅋㅋㅋ

 

복잡도

시간 O(N^2) : 이중 for문으로 모든 리스트를 순차적으로 도니까 N^2이다.

공간 O(N) : 모든 점이 기울기가 다르면 기울기 개수만큼의 key가 생겨버린다. 기울기 개수는 곧 모든 점의 개수 =N이니까 O(N)