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

문제

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

다솜이는 선거에 출마했는데, 자신을 제외한 다른 후보들도 있습니다. 각 후보의 득표 수가 주어졌을 때, 다솜이가 다른 후보들보다 많은 표를 얻기 위해 최소 몇 명의 유권자를 매수해야 하는지 구하는 문제입니다.

다솜이가 매수할 때마다 다른 후보의 득표 수는 1씩 감소하고 다솜이의 득표 수는 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 N = Integer.parseInt(br.readLine());
        int dasom = Integer.parseInt(br.readLine());

        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for (int i = 0; i < N - 1; 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);
    }
}

 

메모리:14372kb 시간:104ms