백준 1417: 국회의원 선거 - 그리디, 우선순위 큐

이 문제는 정렬을 이용해서 풀어도 되지만 우선순위큐를 이용하는 것이 시간복잡도 측면에서 더 효율적입니다.

 

1. 정렬을 이용해서 풀 경우

반복문을 돌 때 마다 자신을 제외한 수들을 내림차순으로 정렬한 후, 해당 값에서 -1을 한 후 자신의 값은 +1 합니다.

이 과정을 반복하다가 최대 값이 자신의 값보다 작게되면 break를 합니다.

 

하지만 정렬을 이용해서 풀게되면 반복문을 돌 때마다 시간복잡도 nlogn의 작업을 해야합니다.

 

2. 우선순위 큐를 이용해서 풀 경우

자신을 제외한 수들을 max heap 형태로 만들어 놓고

반복문을 돌 때마다 pop을 한 후 값을 비교합니다.

만약 pop한 결과 값이 자신의 값보다 크다면 해당 값에서 -1을 한 후 다시 큐에 넣고, 자신의 값은 +1을 합니다.

 

우선순위 큐에서 pop과 push의 시간복잡도는 logn이기 때문에 정렬을 이용해서 풀 때 보다 시간복잡도 측면에서 더 효율적입니다.

 

from sys import stdin
import heapq

input = stdin.readline

candidate = int(input())
my_vote = int(input())
votes = []
for _ in range(candidate-1):
    heapq.heappush(votes, -int(input()))

count = 0
while votes:
    current = -(heapq.heappop(votes))
    if my_vote > current:
        break
    my_vote += 1
    heapq.heappush(votes, -(current-1))
    count += 1

print(count)