[Algorithm/Java] 백준 1417번 - 국회의원 선거

---

https://www.acmicpc.net/problem/1417

---

🔍 문제 풀이

알고리즘 선택

• 다솜이가 1등이 될 때까지, 현재 가장 많은 표를 가진 후보에게서 표를 하나씩 빼서 다솜이에게 준다.
• 가장 많은 표를 가진 후보를 효율적으로 찾기 위해 `우선순위 큐를 사용한다.
• 우선순위 큐는 기본적으로 오름차순 정렬이므로, Collections.reverseOrder()로 내림차순 설정 필요.
• 후보 수가 1명인 경우에는 표를 줄 필요가 없으므로 0 출력.

배운 점

최댓값이나 최솟값을 순차적으로 처리해야 할 경우, 우선순위 큐를 사용하자

• PriorityQueue<>(Collections.reverseOrder()) → 최대 힙
• PriorityQueue<>() → 최소 힙 (기본)

💻 전체 코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int dasom = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

        for (int i = 1; i < n; i++) {
            pq.offer(Integer.parseInt(br.readLine()));
        }

        int cnt = 0;
        while(!pq.isEmpty() && pq.peek() >= dasom){ // 다솜이가 1등이 아닐 동안 반복
            int max = pq.poll(); // 현재 1등 꺼냄
            max--;
            dasom++;
            cnt ++;
            pq.offer(max);
        }
        System.out.println(cnt);



    }
}