[백준] 1417번: 국회의원 선거 (Java) / 우선순위 큐

📍 문제 링크

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

1417번: 국회의원 선거

 

📍 문제 보기 (더보기 👇🏻)

 

📍 문제 접근 

 

국회의원 당선 조건이 다솜이를 제외한 모든 후보자들의 득표수 보다 많아야 한다.

우선순위 큐를 만들어서 다솜이를 제외한 후보자들의 득표 수를 넣었다.

다솜이의 투표수가 가장 높을 때 까지 아래의 과정을 반복하면 된다.

 

1. 큐의 가장 우선순위 값(고 득표자)과 다솜이 표 비교

2. 고득표자 -1 👉🏻 다솜이 표, 매수 횟수 +1 👉🏻 고득표자-1 큐에 넣기

 

point ) 예제 입력 3과 같이 후보자수가 다솜이 혼자인 경우를 고려해야 한다.

 

📍 코드 보기 (더보기 👇🏻)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine()); // 후보자 수
        // 후보자 표를 담을 우선순위 큐 생성(내림차순)
		PriorityQueue<Integer> candidate = new PriorityQueue<>(Collections.reverseOrder());
		int d = Integer.parseInt(br.readLine()); // 다솜이 표
		int cand = 0; // 다른 후보자들이 받은 표
		int best = 0; // 최고 순위인 표 수
		int cnt = 0; // 매수한 횟수

		for (int i = 0; i < t - 1; i++) {           
			cand = Integer.parseInt(br.readLine());
			candidate.add(cand);
		}

		if (t != 1) {                                // 후보자 수가 1명이 아닌 경우
			while (d <= candidate.peek()) {      // 다솜 <= 고 득표자 인 동안
				best = candidate.poll();       // 고 득표자를 꺼내서 
				best--;                        // 투표수 1을 감소 시키고
				cnt++;                         // 매수 횟수 1 증가
				d++;                           // 다솜이 표 1 증가
				candidate.add(best);           // 표가 1개 감소된 후보자를 다시 큐에 넣기

			}
			System.out.println(cnt);
		} else {                              // 후보자 수가 1명인 경우 매수 횟수 0 출력 
			System.out.println(0);
		}

	}

}

 

📍 코드 풀이

reverseOrder(); 내림차순으로 정렬해주는 메서드

peek(); 가장 우선순위인 값을 읽는다. 비어있는 경우 null을 반환. (큐에서 제거 x)

poll(); 가장 우선순위인 값을 읽고, 큐에서 제거. 비어있는 경우 null을 반환.