BOJ(백준) 1417[국회의원 선거]

안녕하세요, 이번 글에서는 백준 1417번 문제인 “국회의원 선거” 문제를 함께 해결해 보겠습니다. 이 문제는 다솜이가 국회의원이 되기 위해 필요한 최소 득표수를 계산하는 문제입니다. 함께 문제를 분석하고, 접근 방법을 정리한 후, 최종적인 정답 코드를 확인해 보겠습니다.

 

문제 URL: https://www.acmicpc.net/problem/1417

 

1. 문제 설명

1) 문제 개요

• 다솜이는 국회의원 선거에 출마했습니다.

• 다솜이 이외의 다른 후보들이 존재하며, 다솜이가 가장 많은 득표수를 가져야만 당선될 수 있습니다.

• 다른 후보의 득표수 중 다솜이보다 많은 득표수를 가진 후보들의 표를 빼앗는 방식으로 다솜이의 득표수를 늘려야 합니다.

• 이때, 다솜이가 최소 몇 표를 더 받아야 하는지 계산하는 문제입니다.

 

2) 입력

• 첫 번째 줄에 후보의 수 N이 주어집니다. (1 ≤ N ≤ 50)

• 두 번째 줄부터 N개의 줄에 각 후보의 득표수가 주어집니다.

• 첫 번째 줄에 주어지는 득표수는 다솜이의 득표수입니다.

 

3) 출력

• 다솜이가 가장 많은 득표수를 가지기 위해 필요한 최소 득표수를 출력합니다.

2. 접근법

1) 입력받기

• sys.stdin.readline을 사용하여 입력 속도를 높입니다.

• 첫 번째 줄에서 후보의 수 N을 입력받습니다.

• 두 번째 줄에서 다솜이의 득표수를 입력받고, 나머지 후보들의 득표수를 우선순위 큐에 저장합니다.

 

2) 우선순위 큐 사용

• 다른 후보들의 득표수를 내림차순으로 정렬하여 가장 많은 득표수를 가진 후보의 표를 빼앗습니다.

• 이를 위해 파이썬의 PriorityQueue를 사용하여 최대 힙으로 구현합니다.

• 큐에서 가장 큰 값을 꺼내어 다솜이의 득표수를 증가시키고, 상대 후보의 득표수를 감소시켜 다시 큐에 넣습니다.

 

3) 다솜이의 득표수 비교

• 다솜이의 득표수가 현재 가장 많은 득표수를 가진 후보보다 많아질 때까지 반복합니다.

3. 정답 코드

import sys
input = sys.stdin.readline
from queue import PriorityQueue

# 입력으로부터 후보 수를 받아옴
N = int(input())

# 다솜의 현재 득표수 초기화
dasom = 0
# 우선순위 큐 생성 (최대 힙으로 사용하기 위해 음수로 저장)
q = PriorityQueue()
# 다솜이 뽑혀야 하는 투표 횟수 초기화
ans = 0

# 각 후보의 득표수를 입력받음
for i in range(N):
    if i == 0:
        # 첫 번째 입력은 다솜의 득표수
        dasom = int(input())
    else:
        # 다른 후보들의 득표수는 우선순위 큐에 음수로 저장 (최대 힙을 만들기 위해)
        q.put(-int(input()))

# N=1인 경우도 있기 때문에 우선순위큐에 값이 있을때만 수행
while q.qsize() > 0:
    # 현재 가장 많은 득표수를 가진 후보의 득표수를 가져옴
    # (음수로 저장했으므로 다시 양수로 변환)
    num = abs(q.get())
    # 다솜의 득표수가 현재 가장 많은 득표수를 가진 후보보다 많으면 종료
    if dasom > num:
        break
    else:
        # 다솜의 득표수 증가, 상대 후보의 득표수 감소
        num -= 1
        dasom += 1
        ans += 1
        # 득표수가 감소한 상대 후보를 다시 큐에 삽입
        q.put(-num)

# 다솜이 뽑히기 위해 필요한 최소 투표 횟수를 출력
print(ans)

 

4. 코드 설명

1) 입력 받기

• 첫 번째 줄에서 후보의 수 N을 입력받습니다.

• 두 번째 줄에서 다솜이의 득표수를 입력받습니다.

• 나머지 후보들의 득표수를 우선순위 큐에 음수로 저장합니다. 이는 파이썬의 PriorityQueue를 최대 힙으로 사용하기 위함입니다.

 

2) 우선순위 큐 사용

• 큐에서 가장 큰 득표수를 가진 후보의 표를 하나 빼앗아 다솜이의 득표수에 더합니다.

• 빼앗긴 후보의 득표수는 하나 감소된 상태로 다시 큐에 삽입합니다.

• 이 과정을 다솜이의 득표수가 가장 많아질 때까지 반복합니다.

 

3) 결과 출력

• 다솜이가 뽑히기 위해 필요한 최소 득표 횟수를 출력합니다.

 

** 예시 **

[입력]

3

5

7

7

 

[과정]

1. 다솜의 초기 득표수: 5

2. 다른 후보들의 득표수: [7, 7]

 

반복 과정:

1. 가장 많은 득표수를 가진 후보(7)의 득표수에서 1표를 빼앗고 다솜에게 추가:

    - 다솜의 득표수: 6

    - 후보들의 득표수: [6, 7]

    - 추가된 투표 횟수: 1

2. 다시 가장 많은 득표수를 가진 후보(7)의 득표수에서 1표를 빼앗고 다솜에게 추가:

    - 다솜의 득표수: 7

    - 후보들의 득표수: [6, 6]

    - 추가된 투표 횟수: 2

 

[출력]

2

 

*******

 

시간 복잡도 계산

 

1. 입력 받기: O(N)

2. 큐에서 가장 큰 득표수를 꺼내고 다시 넣기: O(M log N), 여기서 M은 빼앗은 총 투표 횟수

 

전체 시간 복잡도는 O(N + M log N)로 볼 수 있습니다. 실제 문제에서는 M이 N보다 클 가능성이 높으므로 O(M log N)로 간주할 수 있습니다.

 

5. Github으로 확인

coTest/BOJ/BOJ01_08_02_1417.py at main · pcy4196/coTest