[백준] 1417. 국회의원 선거

문제

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

1417번: 국회의원 선거

 

설계

- heap을 음수로 변환하여 0번째 index와 비교한다.

- heap 구조상 0번째 노드의 정렬은 언제나 보장되지만, 그 뒤는 정렬이 되어있지 않을 수 있기 때문이다.

# 국회의원 선거
from heapq import heappop, heappush, heapify

N = int(input())
heap = [int(input()) for _ in range(N)]
vote = heap[0]
heap.pop(0)     # 가장 앞 자리는 vote로 저장, heap에서 제거
cnt = 0         # 몇번 매수했는가?

if N > 1:		# N이 1개만 있는 경우도 있다 (예외 처리)
    for i in range(N - 1):      # 가장 작은수를 앞으로 위치하기 위해 음수로 변환
        heap[i] = heap[i] * -1
    heapify(heap)       # 음수로 변환 후 힙정렬

    while 1:    # 표 비교
        if vote > heap[0] * -1:
            break
        else:
            cnt += 1
            vote += 1
            current = heappop(heap)
            heappush(heap, current + 1)     # 현재 heap이 음수로 저장되어있으므로 + 1
    print(cnt)
else:
    print(0)