[Python/파이썬] 백준 2910번 빈도 정렬

https://www.acmicpc.net/problem/2910

코드

from heapq import heappop, heappush
import sys
input = sys.stdin.readline

n, c = map(int, input().split())
arr = list(map(int, input().split()))

count_dict = dict()
for i in range(n):
    if arr[i] not in count_dict:
        count_dict[arr[i]] = [i, 1]
    else:
        count_dict[arr[i]][1] += 1

hq = []
for k, v in count_dict.items():
    heappush(hq, [-v[1], v[0], k])

while hq:
    cnt, init, num = heappop(hq)
    for i in range(-cnt):
        print(num, end=" ")

 

자료구조를 사용해서 풀이할 수 있었던 문제였다. 과정은 크게 두 개로 나뉜다.

1. 딕셔너리 사용해서 빈도수 구하기

배열에 나타나는 숫자를 key로 하는 딕셔너리를 만들고, 거기에 value로 `[처음 나타난 시점, 빈도]`를 체크해주면 된다.

 

2. 최소힙에 넣기

빈도수가 높은 순, 빈도수가 같다면 먼저 나타난 순서로 pop될 수 있도록 heap을 만든다.

 

3. 최소힙에 있는 원소를 하나씩 pop하여 출력

2번에서 만든 최소힙을 하나씩 pop하며 빈도수만큼 출력해준다.