백준 1417 국회의원 선거

1417번: 국회의원 선거

기본적으로 과반수가 아닌, 가장 많은 득표를 얻어야 하는 조건이므로, 가장 많은 득표를 올린 사람의 표를 하나씩 자신의 득표로 옮기는 과정을 통해 쉽게 풀어낼 수 있습니다.

 

문제 코드 

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

public class boj1417 {
    public int solution()throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 입력부
        int candidates = Integer.parseInt(br.readLine());
        // 첫줄이 내 득표수
        int myVote = Integer.parseInt(br.readLine());
        // 제일 많은 득표자의 표를 먼저 뻇어야 하니까 (Max 우선순위)
        PriorityQueue<Integer> otherVotes = new PriorityQueue<>(Collections.reverseOrder());
        // 다솜이 빼고 나머지 표
        for (int i = 0; i < candidates - 1; i++) {
            otherVotes.offer(Integer.parseInt(br.readLine()));
        }
        // 알고리즘
        int answer = 0;
        // 단독 후보일 때를 조심하며,
        if (!otherVotes.isEmpty())
            // 나머지 후보들 득표중 최댓값이 나보다 작아질 때까지
            while (otherVotes.peek() >= myVote){
                // 최다 득표자의 득표수
                int votes = otherVotes.poll();
                // 그 사람의 지지자를 한명 매수한다.
                otherVotes.offer(votes-1);
                // 뻇은 표는 내것으로
                myVote++;
                // 매수 진행 횟수
                answer++;
            }

        return answer;
    }

    public static void main(String[] args) throws IOException {
        System.out.println(new boj1417().solution());
    }
}

출력 결과 

입력
3
5
7
7
출력
2