[백준] 1713 - 후보 추천하기

1. 문제

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

1713번: 후보 추천하기

 

2. 접근

1. 이 문제는 문제의 지문을 따라서 그대로 구현하면 된다.

2. 추천 받기 { candidate 는 dict임을 인지 }

 

2.1 -> 추천을 받은 것중 candidate에 없다

2.1.1 -> len(candidate) 과 n을 비교해서 n보다 크거나 같다

2.1.1.1 -> heap으로 가장 작은값을 제거

2.1.1.2 -> 새롭게 heap에 데이터 추가

 

2.2 ->추천을 받은 것중 candidate에 있다 

2.2.1 -> candidate의 value값 증가

 

3. 남은 것들을 사전순으로 정렬해서 출력

 

이 문제는 재밌었다. stack -> queue -> heap 순서로 시도해봤다

 

3. 풀이

#1713 실버1
import sys
input = sys.stdin.readline
#from collections import deque
import heapq

n = int(input())
m = int(input())

candidate = {}
orders = list(map(int,input().split()))

for order in orders:
    if order not in candidate:
        if len(candidate) >= n:
            a = heapq.nsmallest(min(candidate), candidate, key=candidate.get)
            candidate.pop(a[0])
        candidate[order] = 1
    else:
        candidate[order] += 1

for ans in sorted(candidate.keys()):
    print(ans, end=' ')


# 틀린 풀이 -> 내가 생각했던 로직
# [인덱스, 값]
q = deque([])

for order in orders:
    if len(q) <= n:
        time = len(q)
        while True:
            if time == 0:
                break
            
            idx, value = q.popleft()
            
            if idx == order:
                value += 1
            
            q.append([idx,value])
            time -= 1

        q.append([order,1])
        if len(q) > n:
            cnt = m+1
            check = 0
            for _ in range(len(q)-1):
                idx, value = q.popleft()
                
                if value < cnt:
                    cnt = value
                    check = idx
                
                q.append([idx,value])
            
            if cnt >= 2:
                q.popleft()
            # else:
            #     for i in range(len(q)-1):
            #         if check == q[i][0]:
            #             q.pop(i)