파이썬 | 백준 | 1713 | 후보 추천하기 | defaultdict(int)

solution

1. 우선순위 큐 이용

(추천 횟수, 몇 번째 추천인지, 후보 번호) --> 안 돼서 다시 해봐야함

# 1713, 후보 추천하기
import sys
import heapq
# 횟수, 오래, 학생
n = int(sys.stdin.readline())
k = int(sys.stdin.readline())
recommend = list(map(int, sys.stdin.readline().split()))

heap = []
candidate = {}
for i in range(len(recommend)):
    # 사진에 없는 사람 추천 받은 경우
    if candidate.get(recommend[i]) is None:
        # 사진이 꽉차있으면 1) 횟수 비교 2) 최근에 추천받은지 비교
        if len(candidate) == n:
            rm_candidate = heapq.heappop(heap)[2]
            # 후보에서 제거
            del(candidate[rm_candidate])
        candidate[recommend[i]] = 1
        heapq.heappush(heap, (1, i, recommend[i]))
    # 이미 추천 받은 사람
    else:
        candidate[recommend[i]] += 1
        heap_tmp = []
        while heap[0][2] != recommend[i]:
            heapq.heappush(heap_tmp, heapq.heappop(heap))
        heapq.heappush(heap, (candidate[recommend[i]], i, heapq.heappop(heap)[2]))
        while heap_tmp:
            heapq.heappush(heap, heapq.heappop(heap_tmp))
final = []
while heap:
    final.append(heapq.heappop(heap)[2])
print(*sorted(final))

2. 배열, 딕셔너리 이용

# 1713, 후보 추천하기
import sys
from collections import defaultdict

n = int(sys.stdin.readline())
k = int(sys.stdin.readline())
recommend = list(map(int, sys.stdin.readline().split()))

recommend_cnt = defaultdict(int)
candidate = []

for r in recommend:
    recommend_cnt[r] += 1
    if r in candidate:
        continue

    if len(candidate) < n:
        candidate.append(r)
        
    else:
        min_ = 1000
        t = 0
        for tmp in candidate:
            if recommend_cnt[tmp] < min_:
                min_ = recommend_cnt[tmp]
                t = tmp
        del(recommend_cnt[t])
        candidate.remove(t)
        candidate.append(r)


print(*sorted(candidate))

문제 출처 www.acmicpc.net/problem/1713

1713번: 후보 추천하기