[백준/Python] (S5) 국회의원 선거 - 1417

Baekjoon Online Judge의 1417번 국회의원 선거 문제의 Python 풀이입니다.

1417번: 국회의원 선거

💻코드

import heapq 

# 후보의 수 입력받기
n = int(input())
# 다솜이의 초기 득표수 입력받기
dasom_votes = int(input())

# 다른 후보들의 득표수를 저장할 리스트 초기화 및 입력받기
other_votes = [-int(input()) for _ in range(n - 1)]
# 최소 힙 구조로 변환
heapq.heapify(other_votes)

# 매수해야 하는 최소 인원 수
buy_count = 0

# 다른 후보들의 득표수가 남아있는 동안 반복
while other_votes:
    # 가장 득표수가 많은 후보의 득표수를 가져옴 (음수로 저장되어 있으므로 부호를 바꿔줌)
    top_votes = -heapq.heappop(other_votes)
    
    # 가장 득표수가 많은 후보의 득표수가 다솜이의 현재 득표수보다 많거나 같다면 매수 진행
    if top_votes >= dasom_votes:
        # 매수 인원 수 증가
        buy_count += 1
        # 매수한 후보의 득표수를 1 감소시키고 다시 힙에 추가
        heapq.heappush(other_votes, -(top_votes - 1))
        # 다솜이의 득표수를 1 증가시킴
        dasom_votes += 1
    else:
        # 다솜이의 득표수가 이미 최대인 경우 반복 종료
        break

# 매수해야 하는 최소 인원 수 출력
print(buy_count)

🧠풀이

heapq를 이용한 풀이

🤔느낀 점

heapq를 이용한 풀이...