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

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

1. 알고리즘! 생각해보자

1) 내림차순 정렬되어 있는 priority queue 를 사용
2) queue 가 비어있지 않고, dasom 의 득표수보다 많으면
- queue 에서 poll -1 해서 add
- dasom 득표수 증가
- count 증가
3) return count

2. 해결 코드

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

class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		// 입력 및 pq 삽입
		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 count = 0;
		while (!pq.isEmpty() && pq.peek() >= dasom) {		
			++dasom;
			pq.add(pq.poll() - 1);
			++count;
		}

		System.out.println(count);
	}
}

3. 레퍼런스

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