백준 1417번 국회의원 선거 [JAVA]

1417번: 국회의원 선거

 

# 풀이 방법

국회의원 후보들 중 다솜이가 당선되어야 하기 때문에

현재 가장 많은 투표수를 가지고 있는 후보의 표를 다솜이에게 주면서 표수를 확인하는 방식으로 문제를 풀었습니다.

 

후보 수와 그 후보의 득표 수를 저장할 info 객체를 하나 만들어 다솜이를 제외한 후보의 정보를 우선순위 큐에 넣어주었습니다.

 

while문을 돌면서 우선순위 큐가 비었거나, 다솜이를 제외한 후보들 중 가장 많은 득표수를 가지고 있는 후보와 다솜이의 득표수를 비교해 다솜이가 더 많다면 더 이상 매수할 필요가 없으니 반복문을 종료했습니다.

반대로 다솜이보다 득표수가 많다면 그 후보의 표를 다솜이에게 주기 위해 -1 / +1을 하면서 다솜이의 득표수가 가장 많아질 때까지 반복해 주었습니다.

 

# 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
 
public class Main_BJ_1417_국회의원선거 {
    
    static class Info{
        int number, vote;
 
        public Info(int number, int vote) {
            this.number = number;
            this.vote = vote;
        }
    }
    
    static int N;
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PriorityQueue<Info> pq = new PriorityQueue<>(new Comparator<Info>() {
 
            @Override
            public int compare(Info o1, Info o2) {
                return (o1.vote-o2.vote)*-1;
            }
        });
        
        N = Integer.parseInt(br.readLine());
        
        Info dasom = new Info(1, Integer.parseInt(br.readLine()));
        for(int i=2;i<=N;i++) {
            pq.add(new Info(i, Integer.parseInt(br.readLine())));
        }
        
        int count=0;
        while(true) {
            if(pq.isEmpty()||dasom.vote>pq.peek().vote) break;
            
            Info temp = pq.poll();
            dasom.vote=dasom.vote+1;
            pq.add(new Info(temp.number, temp.vote-1));
            count++;
        }
        
        System.out.println(count);
 
    }
 
}