[Python] 수 정렬하기, 수 정렬하기 2

 

문제 3줄 요약

1. N개의 수를 오름차순으로 출력한다.

2. 수는 중복되지 않는다.

3. 왼쪽 문제는 N이 1000이하, 오른쪽 문제는 N이 100만 이하이다.

 

같은 기능을 하는 문제지만,

Input으로 들어올 수 있는 사이즈가 다른 문제였다.

 

두 문제 모두

python 리스트의 sort로 푼 코드들이 있는 것 같다.

python sort 함수 Timsort라는 정렬 알고리즘을 사용하는데

Quicksort와 같이 평균 시간 복잡도가 O(NlogN) 이지만,

최악의 경우는 더 빠른 O(NlogN) 이라고 합니다.

 

https://realpython.com/sorting-algorithms-python/#the-timsort-algorithm-in-python

Sorting Algorithms in Python – Real Python

 

때문에 sort를 사용해도 되지만!

오름차순 하니 딱 떠오르는 자료구조,

heapq 자료구조를 사용하여 값을 오름차순으로 출력하였다.

 

from sys import stdin
import heapq

if __name__ == "__main__":
    N = int(stdin.readline())
    num_q = []

    for _ in range(N):
        heapq.heappush(num_q, int(stdin.readline()))
    
    while(len(num_q) != 0):
        print(heapq.heappop(num_q))

 

heapq는 완전이진트리를 사용하여

값을 추가, 삭제하기 때문에 시간복잡도는 리스트보다 느린 O(logN)입니다.

하지만 오름차순으로 정렬되어 저장하는 자료구조 이기 때문에

문제에서 필요한 오름차순 기능과 시간 제한에는 충분합니다!

 

끝!