백준 문제 풀이 - 수 정렬하기 2 2751번

📜 문제 이해하기

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

💡 문제 재정의

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.
(단, 이 문제의 경우 O(nlogn)만큼 시간이 걸려야 한다.)

✏️ 계획 수립

파이썬에 구현된 heapsort를 사용하면 문제를 쉽게 풀 수 있다.

💻 계획 수행

import sys
import heapq

if __name__ == '__main__':
    N = int(sys.stdin.readline())
    heap = []

    for _ in range(N):
        heapq.heappush(heap, int(sys.stdin.readline().rstrip()))

    while heap:
        print(heapq.heappop(heap))

🤔 회고

이 문제를 풀 때 실수할 수 있는게 퀵소트를 사용하면 안된다는 것이다. 퀵소트는 이름 때문에 가장 빠른 정렬이라고 생각할 수 있는데 최악의 경우 O(n^2)의 시간이 걸리기 때문에 최적알고리즘인 힙소트 또는 머지소트를 사용해야 한다.