[백준 BOJ] 1417 : 국회의원 선거 - python

오늘 풀 문제는 국회의원선거이다.

문제

매수라니 문제가 재밌어서 가져왔다ㅋㅋ

풀이과정

가장 득표수가 많은 사람을 계속 확인해서 매수해서 다솜이의 득표수를 올리는 걸 반복하다가 제일 득표수가 많은 사람이 다솜이보다 득표수가 낮아지는 순간 매수를 멈추면 된다고 생각했다.

그러면 '가장 득표수가 많은 사람'을 알아야 하는데, 이에 적합한 자료구조가 있다. 바로 힙!

이렇게 최대, 최소를 계속 알아야하는 문제는 힙으로 풀자고 기억해놔서 쉽게 떠올릴 수 있었다.

알고리즘을 간략하게 설명하면

1. 다솜이의 처음 득표수를 dasom_votes에 저장해놓는다.
2. 다른 사람의 처음 득표수는 힙에 push해놓는다.
3. 다솜이의 득표 수가 1등이 될 때 까지 아래를 반복한다.
   1. 힙에서 현재 가장 많은 득표수를 가진 사람을 뽑는다.
   2. 매수해서 다솜이의 득표수를 +1 하고 1의 값은 -1을 하고 다시 힙에 push한다.

최종 코드

import heapq

n = int(input())

hq = []
for i in range(n):
    votes = int(input())
    if i == 0:
        dasom_votes = votes
        continue

    heapq.heappush(hq, -votes)

bribe_count = 0
while hq:
    votes = -heapq.heappop(hq)
    if votes < dasom_votes:
        break

    dasom_votes += 1
    bribe_count += 1
    heapq.heappush(hq, -(votes - 1))

print(bribe_count)

결과는 통과~

다른 사람의 풀이

힙을 사용하지 않고 리스트에서 max()를 이용해서 푼다든가
계속 sort를 해서 푸는 풀이도 있었지만 힙을 사용하는 것보다 시간 복잡도를 줄이는 방법은 찾지 못했다.
힙을 사용하는 방법들은 위 풀이와 거의 똑같아서 따로 코드를 첨부하진 않겠다!