[파이썬] 백준 2751 : 수 정렬하기 2

백준 2751 : 수 정렬하기 2 바로가기

합병 정렬을 활용한 풀이

입력의 개수가 1 ≤ N ≤ 1,000,000 으로 주어졌기 때문에 시간 복잡도가 $O(n^2)$인 정렬을 사용할 수 없다.

따라서 시간 복잡도가 $O(nlogn)$인 합병 정렬을 활용하여 풀어보았다.
(그러나 여전히 시간 초과 문제가 발생하므로, 입출력시 sys 라이브러리를 사용해야 한다.)

합병 정렬의 로직은 다음과 같다.

1. 재귀를 사용하여 분할한다.
2. 마지막까지 분할되었으면, 각 원소를 비교하여 정렬한다.
3. 분할된 리스트를 정렬시키면서 다시 합병한다.

풀이

import sys

# 입력
n = int(input())
num = []

for i in range(n):
    num.append(int(sys.stdin.readline()))

# 정렬
def merge_sort(left, right):
    if right - left < 2:  # 마지막까지 분할된 경우이므로 return
        return

    mid = (left + right) // 2  # 가운데 인덱스

    # 재귀 호출을 통해 마지막까지 분할
    merge_sort(left, mid)
    merge_sort(mid, right)

    # 합병
    merge(left, mid, right)


def merge(left, mid, right):
    tmp = []
    l, r = left, mid

    # l < mid : 왼쪽에 탐색하지 않은 원소가 남아있다는 뜻
    # r < right : 오른쪽에 탐색하지 않은 원소가 남아있다는 뜻
    while l < mid and r < right:
        if num[l] < num[r]:  # 두 원소 비교 후 더 작은 원소를 tmp에 추가
            tmp.append(num[l])
            l += 1
        else:
            tmp.append(num[r])
            r += 1
    while l < mid:
        tmp.append(num[l])
        l += 1
    while r < right:
        tmp.append(num[r])
        r += 1

    for i in range(left, right):
        num[i] = tmp[i-left]


merge_sort(0, n)

# 출력
for i in range(n):
    sys.stdout.write(str(num[i]) + "\n")

정렬함수를 활용한 풀이

정렬 함수를 사용하면 훨씬 간단하게 풀이 할 수 있다.
리스트의 메소드인 sort() 함수를 사용하면 원래의 리스트가 정렬된 상태로 변경된다.

역시 입출력시 sys 라이브러리를 사용해야 한다.

풀이

import sys

# 입력
n = int(input())
num = []

for i in range(n):
    num.append(int(sys.stdin.readline()))

# 정렬
num.sort()

# 출력
for i in range(n):
    sys.stdout.write(str(num[i]) + "\n")

4688ms가 걸린 버블 정렬에 비해 정렬 함수는 1300ms 밖에 걸리지 않았다.