[Python] 10989번 : 수 정렬하기 3

 

수 정렬하기 1, 2를 이어 3을 풀어보도록 하겠다!

문제 3줄 요약은 아래 링크와 동일하다.

 

https://59travel.tistory.com/65

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

 

기존의 1,2 와 문제는 같지만

3 또한 N의 범위가 다르고, 중복되는 숫자가 존재한다.

 

때문에 이전에 사용했던

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 코드를 사용하면,

메모리 초과가 발생한다.

 

중복으로 있는 수를 담지 말고 따로 카운팅 해야겠다고 생각이 들었으며,

딕셔너리를 이용하여 카운팅하였다.

 

from sys import stdin
import heapq
from collections import defaultdict
 
if __name__ == "__main__":
    N = int(stdin.readline())
    num_q = []
    num_cnt = defaultdict(int)
 
    for _ in range(N):
        num = int(stdin.readline())
        if num_cnt[num] == 0:
            heapq.heappush(num_q, num)
        num_cnt[num] += 1
    
    while(len(num_q) != 0):
        repeat = heapq.heappop(num_q)
        for _ in range(num_cnt[repeat]):
            print(repeat)

 

defaultdict 라이브러리는 딕셔너리와 기능은 같다.

 

하지만

key 값이 미리 선언 되어 있지 않은 값이라면,

dictinary[Key] = 0 과 같이 초기화 시켜준다.

 

때문에

if num_cnt[num] == 0:
    heapq.heappush(num_q, num)
num_cnt[num] += 1

위 처럼 key 값에 해당하는 값이 있는지 없는지 0으로 체크를 해보고

없다면, 처음 heapq에 넣는 값이니 push 해주고 카운트한다.

 

이 외에는 해당 키 값의 카운트만큼

오름차순으로 반복 출력해주는 코드 전부!

 

제출해주면,

끝!