파이썬으로 한 직선 위의 점 개수를 세는 프로그램

문제 설명

좌표 목록이 주어져 있다고 가정해 보겠습니다. 각 좌표는 x와 y 두 값을 가지며, 데카르트 좌표평면 위의 한 점을 나타냅니다. 우리가 구해야 하는 것은 하나의 직선 위에 동시에 놓여 있는 점들의 최대 개수입니다.

예를 들어 입력이 coordinates = [[6, 2], [8, 3], [10, 4], [1, 1], [2, 2], [6, 6], [7, 7]]이라면, [1, 1], [2, 2], [6, 6], [7, 7] 네 점이 하나의 직선(y = x) 위에 위치하고 있으므로 출력은 4가 됩니다.

접근 방법

핵심 아이디어는 간단합니다. 특정 점을 기준점으로 삼고, 그 점에서 다른 모든 점으로 향하는 기울기를 계산합니다. 기울기가 서로 같다는 것은 해당 점들이 기준점을 지나는 같은 직선 위에 있다는 의미이므로, 가장 많이 등장한 기울기의 개수를 세면 됩니다. 수직선의 경우에는 기울기를 무한대(inf)로 처리합니다.

알고리즘 단계

• 결과 변수 res를 0으로 초기화합니다.
• i를 0부터 점 목록의 끝까지 반복하며 각 점을 기준점 (x1, y1)으로 설정합니다.
• 기울기를 저장할 새로운 맵 slopes를 준비하고, 중복 점 카운터 same을 1로 초기화합니다.
• j를 i + 1부터 점 목록의 끝까지 반복하며 비교 대상 점 (x2, y2)를 가져옵니다.
  • x2가 x1과 같으면(수직선인 경우): slopes[inf] := 1 + (slopes[inf] 값, 없으면 0)
  • x1 = x2이고 y1 = y2이면(완전히 같은 점): same := same + 1
  • 그 외의 경우: slope := (y2 − y1) / (x2 − x1)을 계산한 후 slopes[slope] := 1 + (slopes[slope] 값, 없으면 0)
• slopes가 비어 있지 않으면, res := max(res, same + slopes의 모든 값 중 최댓값)으로 갱신합니다.
• 모든 반복이 끝나면 res를 반환합니다.

구현 예시

아래 파이썬 코드를 통해 더 잘 이해할 수 있습니다.

class Solution:
   def solve(self, points):
      res = 0
      for i in range(len(points)):
         x1, y1 = points[i][0], points[i][1]
         slopes = {}
         same = 1
         for j in range(i + 1, len(points)):
            x2, y2 = points[j][0], points[j][1]
            if x2 == x1:
               slopes[float("inf")] = slopes.get(float("inf"), 0) + 1
            elif x1 == x2 and y1 == y2:
               same += 1
            else:
               slope = (y2 - y1) / (x2 - x1)
               slopes[slope] = slopes.get(slope, 0) + 1
         if slopes:
            res = max(res, same + max(slopes.values()))
      return res

ob = Solution()
coordinates = [[6, 2],[8, 3],[10, 4],[1, 1],[2, 2],[6, 6],[7, 7]]
print(ob.solve(coordinates))

입력

[[6, 2],[8, 3],[10, 4],[1, 1],[2, 2],[6, 6],[7, 7]]

출력

4

위 예제에서는 [1, 1], [2, 2], [6, 6], [7, 7] 네 점이 모두 y = x 직선 위에 있으므로 결과로 4가 출력됩니다.

복잡도 분석

모든 점 쌍을 한 번씩 비교해야 하므로 시간 복잡도는 O(n²)입니다. 공간 복잡도는 기준점마다 기울기를 저장하는 맵에 비례하여 O(n)입니다.