[백준] 알고리즘 분류(그리디 알고리즘,JAVA)1417번, 국회의원 선거

문제 링크

1417번: 국회의원 선거

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 1번이 다솜이의 번호입니다.

2. 다솜이는 다른 사람을 매수해서 자신의 표로 바꾸도록 가능합니다.

3. 다른 후보보다 표가 많으면 당선됩니다.

4. 다솜이가 당선되도록 사람을 매수하는 최소 횟수를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 우선순위 큐를 이용하여 다른 후보의 표보다 다솜이의 표가 많을 때까지 매수를 진행합니다.

 

3. 매수를 진행한 횟수를 결과로 출력합니다.

 

 

매수하기!

 

 

다솜이의 표보다 많은 후보가 존재할 때

 

표가 가장 많은 후보를 찍은 사람을 매수하여 다솜이의 표를 증가시킵니다.

 

 

예를 들어

 

다솜이의 표 : 3

 

다른 사람의 표 : 5, 5

 

매수 진행!

 

1번째

 

다솜이의 표 : 4

 

다른 사람의 표 : 4, 5

 

2번째

 

다솜이의 표 : 5

 

다른 사람의 표 : 4, 4

 

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N = 3

다솜이 표 = 5개

 

다른 후보 정보

 

	후보 2	후보 3
표	7	7

 

2. 우선순위 큐를 이용하여 다른 후보의 표보다 다솜이의 표가 많을 때까지 매수를 진행합니다.

 

매수하기!

 

	후보 2	후보 3
표	6	7

후보 2번 1명 매수!

다솜이 표 : 6

 

 

	후보 2	후보 3
표	6	6

후보 3번 1명 매수!

다솜이 표 : 7

 

다솜이의 표가 가장 높으로 당선!

 

3. 매수를 진행한 횟수를 결과로 출력합니다.

매수한 횟수 2를 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• PriorityQueue를 사용하여 다른 후보들의 투표수가 가장 큰 값을 가져옵니다.
• 다솜이가 당선될 때까지 매수를 진행합니다.
• 매수를 진행한 횟수를 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

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

public class Main{
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
        int answer = 0;
        //후보자가 다솜이 1명이 아닐 때
        if(N!=1){
            //다른 후보 투표수 내림차순 우선순위 큐
            PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
            //다른 후보 투표수 저장
            for(int i=1;i<N;i++)
                pq.add(Integer.parseInt(br.readLine()));

            //다른 후보의 사람들 매수 진행!
            while(pq.peek() >= M){
                int cur = pq.poll();
                cur--;	//가장 큰 후보 투표수 -1
                M++;	//다솜이 투표 수 +1
                answer++;	//매수 횟수 +1
                pq.add(cur);
            }
        }
        bw.write(answer + "");	//매수 횟수 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}