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

📌 문제 링크

후보 추천하기

📌 문제를 풀기전 생각 정리

1. queue를 이용해 순서를 기억하고 defaultdict를 이용해 각 후보자의 추천 수 기억
2. 새로운 후보는 무조건 액자에 걸어야 함
3. 액자에 자리가 없을 경우 후보 제거 순서 => 추천수가 가장 적은후보 > 추천 수가 같으면 가장 먼저 들어온 후보 제거
4. 처음에 작성한 소스코드는 입력 예제는 통과 했지만 예외 사항 #1, #2 입력은 통과하지 못했다. => 액자의 후보 중 최소 추천 수, 모든 후보의 추천수가 같을 때 가장 오래 된 후보를 찾는 로직을 제대로 작성하니 예외사항도 통과

📌 코드

from collections import defaultdict
from collections import deque

picture = int(input())
vote = int(input())
vote_lst = map(int, input().split())
vote_queue = deque([])
current_vote_dic = defaultdict(int)

for idx, v in enumerate(vote_lst):
    current_vote_dic[v] += 1
    # 액자에 자리가 없고 액자에 등록되지 않은 새로운 후보라면
    if len(vote_queue) == picture and current_vote_dic[v] == 1:
        sort_vote_dic = sorted(list(current_vote_dic.items())[:-1], key=lambda x: x[1])
        dict_min_key = sort_vote_dic[0][0]

        del current_vote_dic[dict_min_key]
        vote_queue.remove(dict_min_key)

    if current_vote_dic[v] == 1: vote_queue.append(v)

print(*sorted(vote_queue))

📌 예외 사항

#1. 최소 값이 모두 같은 경우(1)
3
7
2 2 3 3 4 4 5
=> 3 4 5

#2. 1이 제거되는 것이 아니라 3이 제거 되어야 함
3
10
1 1 1 1 2 2 2 3 3 4
=> 1 2 4

📌 문제 풀어본 후기

처음에 작성한 소스코드를 제출해도 통과되지 않아서 뭐가 문제이지 여러 테스트 케이스를 입력해봤다. 그러다 문제를 다시 읽었는데 새로운 후보는 무조건 등록 되어야 한다는 문장이 있었고 그 부분을 처리하니 통과할 수 있었다. 해당 문제는 쉽게 풀 수 있는 문제인데 문제를 제대로 읽지 않아 문제의 요구사항을 만족하지 못하는 소스코드를 작성했고 최소값을 구하는 로직도 처음에는 너무 어렵게 접근했던 것 같다. 문제를 집중해서 읽고 이해만 한다면 쉽게 풀 수 있다.