백준 1417번 국회의원 선거 (JAVA)

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

1417번: 국회의원 선거

 

저는 해당 문제를 우선순위 큐를 이용해 해결하였습니다.

다솜이는 기호 1번이기 때문에 첫번째 입력은 pq에 넣지 않고, 나머지는 pq에 넣었습니다.

pq를 꺼내면서 다솜이의 표수보다 높으면 다솜이의 값을 하나 올리고 pq의 앞 값을 하나 줄이고 다시 pq에 넣습니다.

위의 과정을 다솜이의 표수보다 작아질 때 까지 하며 이를 몇번 실행한 것인지를 출력하였습니다.

 

package BOJ.greedy;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.function.Function;

public class BOJ_1417 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Function<String,Integer> stoi = Integer::parseInt;
        int n = stoi.apply(br.readLine());
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        int voteCnt = 0;
        for(int i = 0 ; i < n ; i++){
            if(i == 0){
                voteCnt = stoi.apply(br.readLine());
            }else{
                int num = stoi.apply(br.readLine());
                pq.offer(num);
            }
        }
        int result = 0;
        while(!pq.isEmpty()){
            if(voteCnt <= pq.peek()){
                result++;
                voteCnt++;
                pq.offer(pq.poll() -1);
            }else{
                break;
            }
        }
        System.out.println(result);
    }
}