문제 내용은 입력으로 후보 수와 후보별 투표 수를 받아서, 1번 후보가 가장 큰 값이 되려면 다른 후보들로부터 최소 몇 표를 뺏어와야 하는지 계산한 후, 해당 표의 수를 출력해줘야 한다.
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 IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int count = Integer.parseInt(br.readLine());
int target = 0;
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());
for (int i = 0; i < count; i++) {
if (i == 0) {
target = Integer.parseInt(br.readLine());
} else {
priorityQueue.add(Integer.parseInt(br.readLine()));
}
}
int vote = 0;
while (!priorityQueue.isEmpty()) {
int val = priorityQueue.poll();
if (val >= target) {
priorityQueue.add(val - 1);
target++;
vote++;
} else {
break;
}
}
System.out.println(vote);
}먼저 입력 내용을 쭉 받아준 후 첫 번째 값만 따로 int에 보관해두고 나머지는 우선순위큐에 모두 넣어주면 되는데, 우선순위큐에서 Collections.reverseOrder()를 넣어 선언해서, 가장 큰 값이 가장 먼저 뽑히는 구조로 만들어주자
이후 우선순위 큐를 계속 돌려주면서 최대값이 첫 번째 후보자의 값보다 크다면 1 줄여주고 다시 우선순위 큐에 넣은 뒤, 첫 번째 후보자의 값은 1 늘려주는 식으로 큐를 계속 진행시켜주면, 가장 큰 값이 먼저 1씩 줄어드는 식으로 진행되므로 1번 후보자가 최대값이 되는 순간 최소 표 수를 구할 수 있기 때문에, 최대 표가 되는 순간 뺏은 표 수를 출력해주면 끝이다.
Leave a Reply