[힙, 정렬] 백준 #2571 수 정렬하기 2 - Python

🗂️ 문제

링크: https://www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

 

💡 접근법

N의 범위가 1,000,000이므로 시간복잡도 O(NLogN)을 갖는 정렬 알고리즘을 사용해야 한다.

파이썬 내장 정렬함수, 퀵정렬, 병합정렬, 힙정렬이 제한 시간 내에 해결할 수 있는 알고리즘이다. 이 중 힙정렬을 사용하여 구현한다.

파이썬의 heapq 라이브러리는 최소 힙으로 구현되어 있기 때문에 heap 배열을 생성하여 입력값을 push하고 하나씩 pop하면 된다.

 

😎 내 코드

import heapq
import sys

N = int(sys.stdin.readline())

arr = []
for _ in range(N):
    heapq.heappush(arr, int(sys.stdin.readline()))

for _ in range(N):
    print(heapq.heappop(arr))

 

✅ 정답 확인