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

📖 문제

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

 

 

 

💡  풀이 방식

•  그리디 - 우선순위 큐

. 사람 수를 내림차순으로 정렬하는 우선순위 큐를 만들고, 득표 숫자들을 입력받는다.

. 우선순위 큐를 돌면서 해당 후보의 득표 수가 다솜이 득표 수보다 크거나 같다면, 해당 후보의 득표 수를 1 감소시킨 후 큐에 새롭게 값을 추가한다. 그리고 다솜이의 득표 수를 +1하고, 정답도 +1한다.

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine()) -1;
        int dasom = Integer.parseInt(br.readLine());
        
        // 우선순위 큐 > 내림차순 정렬
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for(int i = 0 ; i < N ; i++) {
            pq.add(Integer.parseInt(br.readLine()));
        }
        
        int answer = 0;
        while(!pq.isEmpty() && pq.peek() >= dasom) {    // 후보가 다솜이보다 크거나 같은 경우
            pq.add(pq.poll() - 1);  // 후보의 득표 수 감소시킨 후 큐에 새로 넣기
            dasom++;    // 다솜 득표 수 증가시키기
            answer++;   // 매수 횟수 +1
        }
        
        System.out.println(answer);
    }
}

 

 

---

💦 어려웠던 점

- 우선순위 큐를 사용할 생각을 하지 못 했다...

 

 

🧐 새로 알게 된 내용

- 우선순위 큐를 사용해서 해당 득표 수와 다솜이의 득표 수를 비교하면서 다솜이의 득표수를 갱신하는 아이디

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 풀이 참고

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

 

 

✔ 과정 설명 굿...

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