[BOJ] 좌표 정렬하기(11650) - PYTHON

(x, y) 좌표의 1차원 배열이 입력으로 들어오면, 이를 오름차순으로 정렬해 출력하는 문제다.

두 좌표의 x값을 비교해 더 작은 좌표가 앞에 오고, 두 좌표의 x값이 같다면 y값을 비교해서 작은 좌표가 앞에 오게 된다.

시간 복잡도: O(NlogN) 

(정렬은 O(N^2)으로 할 수 있지만 N의 최댓값이 100,000이므로 해당 정렬(ex. 버블 / 삽입 / 선택 정렬)을 사용하면 시간 초과가 나게 된다.)

11650번: 좌표 정렬하기

---

풀이과정

O(NlogN)의 시간 복잡도를 가지는 정렬 방법 중 (ex. 퀵/병합/힙 정렬) 병합 정렬을 사용해서 좌표를 정렬했다.

PYTHON3로 채점했더니 시간 초과가 나서 sys모듈을 import 해서 입력받는 속도를 향상하고, pypy3로 제출했더니 통과했다.

---

코드

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=' ')
 

주석 추가

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=' ')