데카르트 좌표평면 위의 점(좌표) 목록이 주어졌을 때, 이 점들이 하나의 직선 위에 놓여 있는지 판별하는 문제를 생각해 볼 수 있습니다.
예를 들어 입력이 coordinates = [(5, 5), (8, 8), (9, 9)]라면, 세 점 모두 기울기가 1인 직선 위에 있으므로 결과는 True가 됩니다.
문제 해결 접근 방법
두 점만 있으면 항상 직선을 이루므로, 세 번째 점부터 나머지 모든 점이 앞의 두 점과 같은 직선 위에 있는지만 검사하면 됩니다. 기울기를 직접 나누어 계산하면 분모가 0이 되는 경우(수직선)를 따로 처리해야 하므로, 아래와 같은 교차 곱(cross product) 조건식을 사용하는 것이 안전합니다.
- (x0, y0) := 첫 번째 좌표 coordinates[0]
- (x1, y1) := 두 번째 좌표 coordinates[1]
- i를 2부터 좌표 목록 크기 - 1까지 반복:
- (x, y) := coordinates[i]
- 만약 (x0 - x1) * (y1 - y) != (x1 - x) * (y0 - y1) 이라면
- False 반환 (세 점이 한 직선 위에 없음)
- 반복이 끝나면 True 반환 (모든 점이 한 직선 위에 있음)
구현 예제
class Solution: def solve(self, coordinates): (x0, y0), (x1, y1) = coordinates[0], coordinates[1] for i in range(2, len(coordinates)): x, y = coordinates[i] if (x0 - x1) * (y1 - y) != (x1 - x) * (y0 - y1): return False return True ob = Solution() coordinates = [[5, 5],[8, 8],[9, 9]] print(ob.solve(coordinates))
입력
[[5, 5],[8, 8],[9, 9]]
출력
True
동작 원리 설명
두 점 (x0, y0)과 (x1, y1)을 지나는 직선 위의 점 (x, y)는 다음 등식을 만족해야 합니다.
(x0 - x1) * (y1 - y) == (x1 - x) * (y0 - y1)
이 식은 기울기를 나눗셈 없이 비교하는 방식으로, 세 점이 이루는 삼각형의 면적이 0이라는 의미와 같습니다. 따라서 어떤 점이든 이 조건을 벗어나면 그 점들은 직선을 이루지 않으므로 즉시 False를 반환하고, 모든 점이 조건을 통과하면 True를 반환합니다.
이 알고리즘의 시간 복잡도는 O(n), 공간 복잡도는 O(1)로, 점의 개수가 많아도 효율적으로 처리할 수 있습니다.