백준 1417번: 국회의원 선거

선거를 위한 투표를 진행하여 가장 많은 표를 받은 후보가 당선이 된다. N명의 후보에게 각각 몇명이 투표를 할 지 정해져 있을 때,  1번 후보가 당선되기 위해 매수해야 할 사람의 수의 최솟값을 구하는 문제이다.

 

단일 후보라면 매수할 필요가 없다. 단일 후보가 아니라면 1번 후보가 득표수가 가장 많아질 때 까지 우선순위 큐를 사용하여 가장 많이 득표할 후보의 표를 1개씩 1번 후보가 매수한다.

PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
for (int i = 0; i < n - 1; i++) {
    pq.add(Integer.parseInt(br.readLine()));
}
int count = 0;
while (current <= pq.peek()) {
    current++;
    pq.add(pq.remove() - 1);
    count++;
}

 

 

결과 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;

public class 국회의원선거1417 {
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int current = Integer.parseInt(br.readLine());
        if (n == 1) {
            System.out.print("0");
            return;
        }
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for (int i = 0; i < n - 1; i++) {
            pq.add(Integer.parseInt(br.readLine()));
        }
        int count = 0;
        while (current <= pq.peek()) {
            current++;
            pq.add(pq.remove() - 1);
            count++;
        }
        System.out.print(count);
    }
}