points라는 리스트에 데카르트 좌표점들이 담겨 있다고 가정해 보겠습니다. 이 점들을 극각(polar angle)을 기준으로 정렬해야 합니다. 극각의 범위는 0부터 2π까지이며, 만약 여러 점이 동일한 극각을 가진다면 원점으로부터의 거리를 기준으로 정렬합니다.
예를 들어 입력이 다음과 같다면,
points = [(1,1), (1,-2), (-2,2), (5,4), (4,5), (2,3), (-3,4)]
출력 결과는 다음과 같습니다.
[(5, 4), (1, 1), (4, 5), (2, 3), (-3, 4), (-2, 2), (1, -2)]
해결 방법
이 문제는 다음 단계에 따라 해결할 수 있습니다.
- 키(key) 비교 함수를 정의합니다. 이 함수는 좌표점 x를 인자로 받습니다.
- atan := x[1]/x[0]의 아크탄젠트(tan⁻¹) 값을 계산합니다.
- atan ≥ 0이면 (atan, x[1]² + x[0]²) 튜플을 반환하고, 그렇지 않으면 (2π + atan, x[0]² + x[1]²) 튜플을 반환합니다.
- 정의한 key() 함수를 기준으로 points 리스트를 정렬합니다.
핵심 개념 이해하기
Python의 math.atan2(y, x) 함수는 두 인자의 부호를 모두 고려하여 사분면 전체 범위에서 각도를 계산하므로, 단순한 math.atan(y/x)보다 안전하게 사용할 수 있습니다. 다만 atan2의 반환값은 −π ~ π 범위이기 때문에, 음수인 각도에 2π를 더해 0 ~ 2π 범위로 변환해 주어야 합니다. 또한 튜플의 두 번째 요소로 원점까지의 제곱거리(x² + y²)를 함께 반환하면, 극각이 같은 점들은 자동으로 거리순으로 정렬됩니다.
구현 예시
아래 코드를 통해 더 잘 이해할 수 있습니다.
import math
def solve(points):
def key(x):
atan = math.atan2(x[1], x[0])
return (atan, x[1]**2+x[0]**2) if atan >= 0 else (2*math.pi + atan, x[0]**2+x[1]**2)
return sorted(points, key=key)
points = [(1,1), (1,-2),(-2,2),(5,4),(4,5),(2,3),(-3,4)]
print(solve(points))입력
[(1,1), (1,-2),(-2,2),(5,4),(4,5),(2,3),(-3,4)]
출력
[(5, 4), (1, 1), (4, 5), (2, 3), (-3, 4), (-2, 2), (1, -2)]