99클럽 코테 스터디 24일차 TIL

문제

BOJ 1417 - 국회의원 선거

해결 방법

1. 우선순위 큐를 사용하여 다솜이가 다른 후보들보다 커지는 경우를 구한다.

정답 코드 - JAVA

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> q = new PriorityQueue<>(Collections.reverseOrder());
        int dasom = Integer.parseInt(br.readLine());
        int ret = 0;
        for (int i = 1; i < N; i++) {
            q.add(Integer.valueOf(br.readLine()));
        }
        while (!q.isEmpty() && dasom <= q.peek()) {
            int get = q.poll();
            get--;
            dasom++;
            ret++;
            q.add(get);
        }

        bw.write(String.valueOf(ret));
        bw.flush();
    }
}

오늘의 회고

우선순위 큐를 사용하면 쉽게 해결할 수 있는 문제였다.