[🥈5 / 백준 2751 / 파이썬] 수 정렬하기 2 (합병 정렬)

 

2751번: 수 정렬하기 2

 

문제

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

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

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

 

예제 입력 5 5 4 3 2 1

예제 출력 1 2 3 4 5

 

 

풀이

 

이전 문제보다 수의 범위와 입력 개수가 급격히 늘어났다.

따라서, 좀 더 효율적으로 정렬하는 코드를 짜지 않으면 시간 초과가 뜰 것이다.

 

여러 코드들 중에서 O(nlog₂n)의 시간복잡도를 가지는 합병 정렬(merge sort)를 쓸 것이다.

 

합병 정렬은 리스트를 데이터가 하나가 남을 때까지 분할한 뒤, 조금씩 합병하며 정렬하는 정렬 방법이다.

분할과 합병을 반복한다는 점에서 재귀적 방법을 이용할 수 있다는 점을 알 수 있다.

 

우선, 분할하는 부분 먼저 생각해보자.

 

8 7 3 4 2 1 6 5

8 7 3 4       2 1 6 5

8 7      3 4      2 1     6 5

8    7    3    4    2    1    6    5

 

위와 같은 방법으로 입력된 데이터를 분할해줄 것이다.

 

def merge_sort(L):
    if len(L) == 1:
        return L
    
    mid = len(L)//2
   
    left = merge_sort(L[:mid])
    right = merge_sort(L[mid:])

 

데이터의 개수가 1인 경우가 base case가 된다.

 

주어진 데이터의 중간 지점을 정하고, 그 기점을 중심으로 좌, 우로 분해한다.

그리고 합병을 하며 정렬해주면 된다.

 

8, 7, 3, 4 를 합병하는 경우를 생각해보자.

 

우선 8, 7 이 합병되며 78 로 정렬되고 3, 4는 그대로 34로 합병된다.

 

이후 78, 34 가 합병되는데 좌 우 모두 정렬되어있는 상태이므로

각각의 가장 왼쪽에 있는 순서대로 비교하며 합병을 진행한다.

 

여기서, 3 4가 우선적으로 리스트에 들어가고 왼쪽 리스트만 남는데

비교 없이 남은 순서대로 왼쪽부터 리스트에 채워주면 된다.

 

 

아래는 최종 코드이다.

 

import sys

def merge_sort(L):
    if len(L) == 1:
        return L
    
    mid = len(L)//2
   
    left = merge_sort(L[:mid])
    right = merge_sort(L[mid:])
    
    i,j = 0,0
    L2 = []
    while ((i < len(left)) and (j < len(right))):
        if left[i] < right[j]:
            L2.append(left[i])
            i+=1
        else:
            L2.append(right[j])
            j+=1
    while i < len(left):
        L2.append(left[i])
        i+=1
    while j < len(right):
        L2.append(right[j])
        j+=1
        
    return L2
    
a = merge_sort([int(sys.stdin.readline()) for i in range(int(sys.stdin.readline()))])
for i in a:
    print(i)