[백준] 2751 수 정렬하기 2

문제

[실버5]
https://www.acmicpc.net/problem/2751

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

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

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

아이디어

2750번과 같은 문제인데, N의 범위가 100만 까지로 매우 넓어졌다.
이를 시간 제한 2초만에 풀으려면 NlogN의 시간복잡도를 가지는 알고리즘을 이용해야 한다.

따라서 병합정렬을 이용하였다.
또는 파이썬 기본 정렬 라이브러리를 이용해도 된다.

• 퀵정렬의 시간복잡도는 O(NlogN)이 아니다. 이는 평균적인 시간복잡도이고, 역순으로 정렬된 데이터 등 최악의 경우 O(N^2)이 된다. 따라서 이 문제에서 퀵정렬을 이용하면 시간초과가 뜬다.

• 파이썬은 1초에 약 2천만번의 연산을 할 수 있다.

풀이

import sys

def merge_sort(array):
    if len(array) <= 1:
        return array
    
    mid = len(array) // 2
    left_array = merge_sort(array[:mid])
    right_array = merge_sort(array[mid:])
    # print("merge_sort" + str(left_array), str(right_array))
    return merge(left_array, right_array)

def merge(left, right):
    merged_array = []
    l, r = 0, 0
    
    while l < len(left) and r < len(right):
        if left[l] < right[r]:
            merged_array.append(left[l])
            l += 1
        else:
            merged_array.append(right[r])
            r += 1
    # print(merged_array, left[l:], right[r:])
    merged_array += left[l:]
    merged_array += right[r:]
    # print(merged_array)
    
    return merged_array

n = int(input())

array = []
for _ in range(n):
    array.append(int(sys.stdin.readline()))
    
sorted_array = merge_sort(array)

# array.sort() # 기본 라이브러리를 이용해도 된다.
for i in sorted_array:
    print(i)

N의 범위가 매우 크기 때문에 입력에서도 시간초과가 뜰 수 있다.
따라서 input()이 아닌 sys.stdin.readline()을 이용해서 입력받아야 한다

아래는 2750 수 정렬하기 코드이다.

퀵정렬을 이용하여 구현하였다.
이 문제 또한 파이썬 기본 라이브러리를 이용하여 구현해도 된다.

import sys
sys.setrecursionlimit(10**4) # 퀵정렬은 재귀를 이용하므로 재귀 깊이를 설정해야 한다.

def quick_sort(array, start, end):
    if start > end:
        return
    pivot = start
    left = start + 1
    right = end
    
    while left <= right: # 엇갈리기 전까지 반복
        # 피벗보다 큰 데이터를 찾을 때까지 반복
        while left <= end and array[left] <= array[pivot]: # left:피벗보다 큰 데이터 선택
            left += 1
        # 피벗보다 작은 데이터를 찾을 때까지 반복
        while right > start and array[right] >= array[pivot]: # right:피벗보다 작은 데이터 선택
            right -= 1
        
        if left > right: # 엇갈렸다면 작은 데이터(right)와 피벗을 교체
            array[right], array[pivot] = array[pivot], array[right]
        else:
            array[left], array[right] = array[right], array[left]
    
    quick_sort(array, start, right - 1)
    quick_sort(array, right + 1, end)

n = int(input())

array = []
for _ in range(n):
    k = int(input())
    array.append(k)
    
quick_sort(array, 0, len(array)-1)
# array.sort()
for i in array:
    print(i)

Comment

처음에 N의 범위가 커진 것을 보고 시간복잡도 O(NlogN)을 가지는 퀵정렬을 이용하여 구현하고 시간초과가 떠서 매우 당황했다. 퀵정렬에서 최악의 경우 시간복잡도 O(N^2)임을 기억하자.

시간복잡도 O(NlogN)을 보장하는 정렬 알고리즘은 병합정렬과 파이썬 기본 라이브러리이다!