백준 #1713 - [S1] 후보 추천하기 : 정렬

(python3)

1713번: 후보 추천하기

 

아이디어

사진 틀이 꽉 차있을 때 새로운 후보가 들어오면 기존 사진틀의 후보 중 우선순위가 가장 낮은 후보를 삭제해야합니다.

우선순위는 1. 득표수 높은 순, 2. 나중에 들어온 순 으로 결정됩니다.

저는 후보 득표를 빨리 올리기 위해서 dict를 사용했고 삭제할 후보를 찾아야할 때 마다 정렬하는 방식으로 해결했습니다.

 

코드

import sys
def solution(input) :
    N = int(input().strip())
    M = int(input().strip())
    L = list(map(int,input().split()))

    P = {} # 사진틀 dict

    for i,l in enumerate(L) :
        if l in P : # 틀에 있는 후보는 득표
            P[l][1] += 1
        else : # 틀에 없는 후보이고
            if len(P) >= N : # 사진틀이 꽉 차있으면
                del P[sorted(P, key = lambda x : (P[x][1], P[x][0]))[0]] # 정렬 후 후순위 후보 삭제
            P[l] = [i,1]
    print(' '.join([str(n) for n in sorted(P)])) # 사진틀에 남은 후보들 번호순 출력
        
input = sys.stdin.readline
solution(input)

 

my solved.ac :

solved.ac