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

---

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

---

🔍 문제 풀이

문제 도식화

알고리즘 선택

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

배운 점

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

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

💻 전체 코드

PQ (우선순위 큐) 사용

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

public class Main {
    static int n, dasom;
    static PriorityQueue<Integer> pq;

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

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

        // n이 1인 경우 예외 처리
        if (n == 1) {
            System.out.println(0);
            return;
        }

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

        int ans = solve();
        System.out.println(ans);
    }

    static int solve(){
        int cnt = 0;

        // 다솜의 표가 다른 후보의 최대 표보다 작거나 같을 때만 반복
        while (dasom <= pq.peek()) {
            int max = pq.poll(); // 현재 1등 꺼냄
                max --; // 값 줄이고
                dasom++;
                cnt++;
                pq.offer(max); // 다시 넣음
            }
        return cnt;
    }
}

그리디 알고리즘

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

public class Main {
    static int[] arr;
    static int n;

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

        n = Integer.parseInt(br.readLine());

        arr = new int[n];
        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }

        int ans = solve();
        System.out.println(ans);
    }

    static int solve(){
        int cnt = 0;

        if (n == 1) {
            return 0;
        }

        while(true){
            int maxVal = Integer.MIN_VALUE;
            int maxIdx = -1;

            // 1. arr[0] 제외 최댓값과 idx 구하기
            for(int i=1; i<n; i++){
                if(arr[i] > maxVal){
                    maxVal = arr[i];
                    maxIdx = i;
                }
            }

            // 2. arr[0]이 최대
            if(arr[0] > maxVal){
                return cnt;
            }

            // 3. 최대 x
            arr[maxIdx]--; // 최다득표자 표 뺏어서
            arr[0]++; // arr[0]에게
            cnt++;
        }
    }
}