문제 설명
이번에 공부한 문제는 2차원 평면 위의 점 N개가 주어졌을 때, 이를 특정 기준에 따라 정렬하는 프로그램을 작성하는 것입니다. 주어진 점들을 y좌표가 증가하는 순서로, y좌표가 같으면 x좌표가 증가하는 순서로 정렬하는 것입니다.
문제 조건
- 점의 개수 N은 1 이상 100,000 이하입니다.
- 각 점의 좌표 ((x_i, y_i))는 -100,000 이상 100,000 이하의 정수입니다.
- 위치가 같은 두 점은 없습니다.
입출력 예
| 입력 | 출력 |
|---|---|
| 5 | 1 -1 |
| 0 4 | 1 2 |
| 1 2 | 2 2 |
| 1 -1 | 3 3 |
| 2 2 | 0 4 |
| 3 3 |
문제 해결 방법
해결 전략
주어진 점들을 y좌표가 증가하는 순서로 정렬하고, y좌표가 같으면 x좌표가 증가하는 순서로 정렬해야 합니다. 이를 위해 Python의 내장 sorted 함수를 사용했습니다.
시간 복잡도
Python의 sorted 함수는 Timsort 알고리즘을 사용하며, 시간 복잡도는 (O(n \log n))입니다. 따라서, 최대 100,000개의 점을 정렬하는 데 적합합니다.
공간 복잡도
주어진 데이터를 리스트에 저장하고 정렬하므로, 공간 복잡도는 (O(n))입니다.
코드 구현
다음은 sorted 함수를 사용하여 문제를 해결하는 Python 코드입니다.
def sort_points():
import sys
input = sys.stdin.read
data = input().split()
N = int(data[0])
points = []
for i in range(1, len(data), 2):
x = int(data[i])
y = int(data[i + 1])
points.append((x, y))
# 정렬 기준: y좌표가 증가하는 순으로, y좌표가 같으면 x좌표가 증가하는 순서로
sorted_points = sorted(points, key=lambda point: (point[1], point[0]))
for point in sorted_points:
print(point[0], point[1])
if __name__ == "__main__":
sort_points()코드 설명
sys.stdin.read를 사용하여 입력을 한 번에 읽고,split()을 사용하여 각 줄을 분리합니다.- 첫 번째 값은 점의 개수인
N이고, 나머지 값들은 점의 좌표입니다. - 좌표들을
(x, y)형태의 튜플로 리스트에 저장합니다. sorted함수를 사용하여 점들을 정렬합니다. 정렬 기준은lambda point: (point[1], point[0])로 설정하여, y좌표를 기준으로 오름차순 정렬하고, y좌표가 같으면 x좌표를 기준으로 오름차순 정렬합니다.- 정렬된 점들을 차례대로 출력합니다.
예시 테스트
- 입력:
5 0 4 1 2 1 -1 2 2 3 3 - 출력:
1 -1 1 2 2 2 3 3 0 4
이 코드는 주어진 모든 조건을 만족하며, 각 입력에 대해 올바르게 동작합니다. sorted 함수를 사용하여 간단하게 정렬 기준을 설정하고, 원하는 순서대로 점들을 출력할 수 있습니다.
결론
이번 문제를 통해 Python의 내장 함수인 sorted를 사용하여 2차원 평면 위의 점들을 효율적으로 정렬하는 방법을 배울 수 있었습니다. sorted 함수는 Timsort 알고리즘을 사용하여 시간 복잡도 (O(n \log n))로 매우 효율적입니다. 이 문제를 해결하면서 정렬 기준을 설정하는 방법과 정렬 알고리즘의 효율성을 다시 한 번 확인할 수 있었습니다. 앞으로도 다양한 정렬 알고리즘을 공부하여 알고리즘에 대한 이해를 더욱 깊게 할 예정입니다.
