백준 2910 - (python)빈도 정렬

www.acmicpc.net/problem/2910

2910번: 빈도 정렬

1. 알고리즘 유형

정렬, 구현

 

2. 자료구조

set, 우선순위큐, 딕셔너리

 

3. 풀이

 

리스트에서 요소마다 반복횟수를 딕셔너리로 만들기

1) count() 함수 사용

 

우선순위큐로 정렬

1) 이미 heapq에 넣으면 set에 추가해서 중복 방지

2) 우선순위의 기준 잡기

 

출력

1) 반복 횟수만큼 출력

 

코드

import sys
import heapq
N, C = map(int, sys.stdin.readline().split())
li = list(map(int, sys.stdin.readline().split()))
diction = {}
pq = []
_set = set()
for i in range(N):
    if not diction.get(li[i]):
        diction[li[i]] = li.count(li[i])
for i in range(N):
    if not li[i] in _set:
        _set.add(li[i])
        heapq.heappush(pq, [-diction[li[i]], i, li[i]])
while pq:
    temp = heapq.heappop(pq)
    for _ in range(-temp[0]):
        print(temp[2], end=" ")