[99클럽 코테 스터디 24일차 TIL] 백준 1417번 국회의원 선거

99클럽 코테 스터디 24일차 TIL

💙 JAVA 비기너

📌 오늘의 학습 키워드

• 힙(우선순위 큐)

📌 공부한 내용

📍 오늘의 문제

📍 작성 코드

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

public class Main {
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder()); 
		
		int N = Integer.parseInt(br.readLine());
		
		int dasom = Integer.parseInt(br.readLine());
		
		for(int i=0; i<N-1; i++) {
			heap.add(Integer.parseInt(br.readLine()));
		}
		
		br.close();
		
		int count = 0;
		while(!heap.isEmpty() && heap.peek() >= dasom) {
			heap.add(heap.poll() - 1);
			dasom++;
			count++;
		}
		
		bw.write(String.valueOf(count));
		
		bw.flush();

        bw.close();
		
    }
}

📌 오늘의 회고

읽자마자 아니 이래도 되는거야?! 싶었던 문제였다.

감자의 생각은 단순했다!

가장 투표수가 높은 녀석의 표를 한표씩 뺏어서 다솜이가 최강이 되게 만들자❗❗

비교가 되어야하는 다솜이의 표는 굳이 heap에 넣지 않고 dasom이라는 변수에 넣어 계속 들고다니면서 비교를 했다.

그래서 0부터 N-1미만으로 for문을 돌려 heap에 투표수를 넣어줬다.

그리고 while문에 가둬 heap이 비어있지 않거나 dasom보다 크거나 같은 수가 없을 때까지 가장 큰 투표수를 빼고 dasom을 증가하고 횟수를 나타내는 count를 증가시켰다.

heap이 비어있거나 더 이상 dasom보다 큰 투표수를 가지고 있는 녀석이 없다면 count 출력!!