[백준] 파이썬 1713 : 후보 추천하기

 

 

"""
31120KB	44ms
"""
# 최종후보를 오름차순으로 출력
# 추천 시작 전에는 사진틀이 비어있음
# 추천하면 사진틀에 올라감
# 비어있는 사진틀이 없는 경우 - 추천횟수가 가장 작은거 삭제하고 추가함. 추천 횟수가 적은 학생이 두명 이상이면 오래된거 삭제함
# 게시된게 추천받으면 추천횟수간 증가
# 게시가 삭제되면 추천횟수는 초기화됨

import sys
input = sys.stdin.readline

n = int(input())
r = int(input())
student = list(map(int, input().split()))
nominee = {}

for i in student:
    # 빈 사진틀이 있을때 - 딕셔너리에 후보 : 추천수 로 추가
    if len(nominee) < n:
        if i in nominee:
            nominee[i] += 1
        else:
            nominee[i] = 1
    # 빈 사진틀이 없을때 - 추천횟수가 가장 작은거 삭제하고 추가 / 이미 있는 후보라면 추천수 증가
    else:
        # 후보가 있는지 없는지 확인. 있다면
        if i in nominee:
            nominee[i] += 1
        else:
            MIN = min(nominee.values()) # 가장 작은 추천수
            for key in nominee.keys():
                if nominee[key] == MIN: # 등록순으로 가장 작은 추천수의 후보 제거
                    del nominee[key]
                    break
            nominee[i] = 1 # 새 후보 추가

for i in sorted(nominee.keys()): # 오름차순으로 정렬하여 후보 출력
    print(i, end=' ')

 

은근히 까다로웠던 문제! 그래도 요구하는 조건대로만 하면 잘 구현할 수 있었다. 

후보들을 어떤 자료형으로 관리할지가 고민이 되었다. 처음에는 이차원 배열로 할까 했는데 최소값을 찾기 힘들것같았고, 그래서 딕셔너리를 사용하기로 했다. 

후보를 담아줄 nominee라는 딕셔너리에 빈 사진틀이 있을경우와 없을 경우로 나누어서 후보들을 넣거나 삭제하고 새 후보를 넣도록 했다. 

 

 

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