BOJ
[BOJ] 좌표 정렬하기(11650) - PYTHON
허비1411
2022. 5. 22. 20:47
(x, y) 좌표의 1차원 배열이 입력으로 들어오면, 이를 오름차순으로 정렬해 출력하는 문제다.
두 좌표의 x값을 비교해 더 작은 좌표가 앞에 오고, 두 좌표의 x값이 같다면 y값을 비교해서 작은 좌표가 앞에 오게 된다.
시간 복잡도: O(NlogN)
(정렬은 O(N^2)으로 할 수 있지만 N의 최댓값이 100,000이므로 해당 정렬(ex. 버블 / 삽입 / 선택 정렬)을 사용하면 시간 초과가 나게 된다.)
11650번: 좌표 정렬하기
첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.
www.acmicpc.net
풀이과정
O(NlogN)의 시간 복잡도를 가지는 정렬 방법 중 (ex. 퀵/병합/힙 정렬) 병합 정렬을 사용해서 좌표를 정렬했다.
PYTHON3로 채점했더니 시간 초과가 나서 sys모듈을 import 해서 입력받는 속도를 향상하고, pypy3로 제출했더니 통과했다.
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
import sys
input = sys.stdin.readline
def compare(a, b):
if a[0] > b[0]:
return 1
elif a[0] == b[0]:
if a[1] > b[1]:
return 1
else:
return 0
else:
return 0
def mergeSort(points):
if len(points) == 1:
return points
mid = len(points) // 2
arr1 = mergeSort(points[0:mid])
arr2 = mergeSort(points[mid:len(points)])
index1 = 0
index2 = 0
rt = []
while len(rt) < len(points):
if index1 >= len(arr1):
rt.append(arr2[index2])
index2 += 1
elif index2 >= len(arr2):
rt.append(arr1[index1])
index1 += 1
else:
if compare(arr1[index1], arr2[index2]) == 1:
rt.append(arr2[index2])
index2 += 1
else:
rt.append(arr1[index1])
index1 += 1
return rt
N = int(input())
points = []
for _ in range(N):
points.append(tuple(map(int, input().split())))
points = mergeSort(points)
for x, y in points:
print(x, y, sep=' ')
|
cs |
주석 추가
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
import sys
input = sys.stdin.readline # input 입력속도 향상
def compare(a, b): # a좌표와 b좌표 비교 (반환값 0: a가 앞으로, 1: b가 앞으로)
if a[0] > b[0]: # x좌표가 a가 크다면
return 1 # 1반환
elif a[0] == b[0]: # x좌표가 같다면
if a[1] > b[1]: # y좌표 비교해서 a가 크다면
return 1 # 1반환
else:
return 0 # 아닌경우 0 반환
else:
return 0 # 아닌경우 0 반환
def mergeSort(points): # points배열을 입력받아 정렬
if len(points) == 1: # 입력받은 배열의 크기가 1이면
return points # 바로 반환
mid = len(points) // 2 # 가운데 위치
arr1 = mergeSort(points[0:mid]) # 배열 두개로 나눈후 재귀호출(앞쪽 절반)
arr2 = mergeSort(points[mid:len(points)]) # 배열 두개로 나눈후 재귀호출(뒷쪽 절반)
index1 = 0 # arr1의 인덱스
index2 = 0 # arr2의 인덱스
rt = [] # 반환값을 저장할 배열
while len(rt) < len(points): # rt배열에 값을 다 담을때까지
if index1 >= len(arr1): # arr1의 값을 다 담았다면
rt.append(arr2[index2]) # arr2의 값을 담기
index2 += 1
elif index2 >= len(arr2): # arr2의 값을 다 담았다면
rt.append(arr1[index1]) # arr1의 값을 담기
index1 += 1
else:
if compare(arr1[index1], arr2[index2]) == 1: # 비교해서 arr2의 값이 더 작다면(왼쪽에 와야한다면)
rt.append(arr2[index2]) # arr2 값 담기
index2 += 1
else: # 아닌경우
rt.append(arr1[index1]) # arr1 값 담기
index1 += 1
return rt # 결과 반환
N = int(input()) # 좌표 갯수
points = [] # 입력 받을 배열
for _ in range(N):
points.append(tuple(map(int, input().split()))) # 좌표들 입력받기
points = mergeSort(points) # 정렬
for x, y in points: # 정렬된 좌표들 출력
print(x, y, sep=' ')
|
cs |