백준 1417번 : 국회의원 선거

[문제 링크]

1417번: 국회의원 선거

시뮬레이션으로 분류되어 있지만, 우선순위 큐를 활용해 풀 수 있는 문제였습니다.

풀이

우선순위 큐는 pop 동작 시 언제나 가장 작거나 큰 값을 내보낸다는 특징이 있습니다.

따라서, 이 속성을 이용해 다음과 같은 시퀀스를 구성합니다.

1. 우선순위 큐 가장 위의 득표수를 1 뺀다.
2. 다솜이의 득표수를 1 올린다.
3. 1번에서 뺀 득표수를 다시 우선순위 큐에 삽입한다.
4. 만약 다솜이의 득표수가 큐의 가장 위의 원소보다 크다면 중단한다.

[정답 코드 - Python]

import heapq
import sys

input = sys.stdin.readline

pq = []
cnt = 0

N = int(input())
G = -int(input())

for i in range(1, N):
    temp = int(input())
    # 우선순위 큐가 내림차순으로 원소를 pop하도록 - 기호를 붙입니다.
    heapq.heappush(pq, -temp)

# 큐가 비어있는 경우에만 반복문을 실행합니다.
while True and pq:
    temp = heapq.heappop(pq)
    if temp <= G:
        temp += 1
        cnt += 1
        G -= 1
        heapq.heappush(pq, temp)
    else:
        break

print(cnt)