[우선순위큐] boj 1417. 국회의원 선거

문제 해석

이 문제는 리스트에서 가장 큰 수를 계속 찾아내어서 값을 빼주고, 이를 비교값에 반영해주면 되는 문제다. N과 M의 크기가 크지 않으므로 단순하게 떠오르는 로직을 구현하면 되는 문제이며, 이를 구현하는 방법을 아는지 묻는 문제인 것으로 보인다.

파이썬에는 최소 힙 이라는 우선순위 큐가 콜렉션으로 구현되어 있고, 이를 이용해 최대 힙으로 사용하여 문제를 풀어낼 수 있다.

문제 풀이

# 국회의원 후보 N명 (1 <= N <= 50)
# 마을주민 M명 (1 <= M <= 100)

# 다른 후보의 득표수보다 많기만 하면 됨

# 다솜이가 매수해야 하는 사람의 최솟값을 출력하는 프로그램을 작성하라.

import sys
input = sys.stdin.readline
from heapq import *

# 기본 변수 및 입력 구성
ans = 0
hq = []
N = int(input())

# 기호 1번을 찍으려고 하는 사람의 수 (입력)
# 기호 2번을 찍으려고 하는 사람의 수 (입력)
# ... N개의 줄에 걸쳐 입력
dasom = int(input())
for i in range(1, N):
    heappush(hq, -(int(input())))

# hq가 비어있지 않으면,
# 아래 과정 반복
# 힙에서 하나 빼고(tmp) dasom이랑 비교
# dasom이 더 크면 break
# dasom이 더 작으면 ans += 1; tmp -= 1; dasom += 1; heappush(hq, -tmp);
if hq:
    while True:
        tmp = -heappop(hq)
        if dasom > tmp: break
        tmp -= 1
        dasom += 1
        heappush(hq, -tmp)
        ans += 1
    print(ans)

# hq가 비어있으면 print(0)
else:
    print(ans)