[Python]2751번, 병합정렬

문제

 

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

 

입력

 

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 

둘째 줄부터 N개의 줄에는 수가 주어진다. 

이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

 

출력

 

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

 

풀이

 

문제의 팁에 병합정렬이나 힙정렬 등으로 풀 수 있으나 내부 정렬을 이용해도 된다고 적혀있다.

 

파이썬의 내부 정렬은 팀정렬이기 때문에 병합정렬만을 사용하는 것보다는 당연히 빠르겠으나,

 

이참에 파이썬으로도 병합정렬을 구현해보기로 마음먹었다.

 

아래는 그 결과물:

 

2023.03.31 - [Development/.py] - [Algorithm]파이썬으로 병합정렬(Merge Sort) 구현하기

[Algorithm]파이썬으로 병합정렬(Merge Sort) 구현하기

알고리즘 정답은 그냥 위에서 구현한 병합정렬을 가지고 와서 조건에 맞게 사용했을 뿐이다.

import sys

n = int(sys.stdin.readline())
list = []
temp = [0] * n

for _ in range(n):
    list.append(int(sys.stdin.readline()))


def merge_sort(list, start, end):
    if start == end:
        return

    mid = (start + end) // 2

    merge_sort(list, start, mid)
    merge_sort(list, mid + 1, end)

    left = start
    right = mid + 1
    idx = left

    while left <= mid and right <= end:
        if list[left] <= list[right]:
            temp[idx] = list[left]
            idx += 1
            left += 1
        else:
            temp[idx] = list[right]
            idx += 1
            right += 1
    if left > mid:
        while right <= end:
            temp[idx] = list[right]
            idx += 1
            right += 1
    else:
        while left <= mid:
            temp[idx] = list[left]
            idx += 1
            left += 1

    for i in range(start, end + 1):
        list[i] = temp[i]


merge_sort(list, 0, len(list) - 1)

print(*list, sep='\n')