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

🚀접근하기

생각보다 생각해야 할 조건이 많았던 문제. 현재 게시된 사진일 경우, 비어있는 사진틀이 없는 경우, 비어있는 사진틀이 있는 경우 모두를 고려해서 코드를 짜야했다.

처음엔 리스트를 이용하려다가, 후보의 숫자와 추천수를 같이 짝지우기 위해 딕셔너리를 선택했다.

🎉코드

import sys
N = int(sys.stdin.readline())
total_num = int(sys.stdin.readline())
num = list(sys.stdin.readline().split())

cand = {}

for i in range(total_num):
    #현재 게시된 사진일 경우
    if cand.get(num[i]): 
        cand[num[i]] += 1
    else:
        #비어있는 사진틀이 없는 경우
        if len(cand) == N:
            min_value = total_num
            for key in reversed(cand.keys()):
                if min_value >= cand[key]:
                    min_value = cand[key]
                    min_key = key    
            #가장 오래된 값 삭제
            cand.pop(min_key)
            #새로 추가
            cand[num[i]] = 1
        else:
            #비어있는 사진틀이 있는 경우
            cand[num[i]] = 1

sorted_keys = sorted(cand.keys(), key = int)

for key in sorted_keys:
    print(key, end=' ')
print()

 

처음엔 문제를 잘못 읽어서 사진틀에 게시된 사진이 삭제되는 경우에도 추천횟수는 그대로 유지되고, 만약 다음에 또 사진틀에 게시될 경우 그 추천횟수에서 +1이 되는 줄 알고 사진틀에서 삭제된 후보의 추천 수는 어떻게 가지고 있지..?라는 생각을 하다가 시간을 낭비했다. 알고보니 사진틀에 게시된 사진이 삭제되는 경우에는 해당 학생이 추천받은 횟수는 0으로 바뀐다.

 

따라서 1) 현재 게시된 사진일 경우 : 추천횟수를 1씩 증가해주었고, 2) 비어있는 사진틀이 없는 경우 (사진틀이 꽉찬 경우) : 딕셔너리를 뒤에서 앞으로 역순으로 조회해 가장 오래된 값을 삭제하고 새로운 값을 추가해주었다. 역순으로 조회한 이유는 딕셔너리가 오래된 순으로 정렬되어 있으니 (오래된 것일수록 앞에) 만약 추천 횟수가 같을지라도 더 앞에 있는 것(더 오래된 것)을 선택하여 삭제할 수 있기 때문이다.

마지막으로 3) 비어있는 사진틀이 있는 경우 : 새로 추천받은 후보를 딕셔너리에 추가해주었다.

 

출력이 최종 후보의 학생 번호를 증가하는 순서대로 출력되어야 하기 때문에, 딕셔너리를 정렬해 주었다. 처음엔 그냥 sorted_keys = sorted(cand.keys()) 이렇게만 했었는데, sorted()함수는 문자열의 사전 순으로 정렬을 수행하기 때문에 '2'보다 '10'이 더 앞에 정렬되는 일이 발생했다. 따라서 정렬기준을 숫자로 변환하기 위해 key = int를 추가해주었다.

 

💪다짐

사실 지금까지 거의 리스트만 사용했던 것 같은데, 이렇게 상황에 따라 리스트 말고도 딕셔너리 같은 다른 자료형을 쓰는 것이 더 문제를 쉽게 풀 수 있구나를 몸소 느꼈다. 문제에 잘 맞는 자료형을 선택하여 쓸 수 있는 능력을 더 길러야겠다.