백준 1417 국회의원 선거 JAVA

자료구조 및 브루트포스(BruteForce)

 

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

1417번: 국회의원 선거

 

Array로 짜나 PriorityQueue로 짜나 시간은 똑같았다.

코드 길이가 확실히 줄어든 PriorityQueue로 정리해보았다.

 

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

public class Subject1417 {

//    3 - 출마한 후보 수
//    5 - 대상 (후보 1) 득표수
//    7 - 후보 2 득표수
//    8 - 후보 3 득표수


    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bf.readLine()); // 후보자수
        if (N == 1) {

            System.out.println(0);
            return;
        }                                       // 후보자 수가 대상 혼자면 매수할 필요가 없음

        int target = Integer.parseInt(bf.readLine()); // 대상 득표수


        PriorityQueue<Integer> candidate = new PriorityQueue<>(Collections.reverseOrder());
        // 다솜이 제외 후보자 다득표수로 정렬할 수 있게
        // array 안쓴 이유 : 내부 배열이 항상 다득표자가 우선 순위로 와야해서.
        // 다득표자가 다음다득표자가보다 득표수가 적어질 경우와 
        // 다음 다득표자가 대상보다 득표수가 많은 경우를 생각했을 때
        // array를 계속 정렬 해줘야하지 않을까 생각함.
        
        for (int i = 0; i < N - 1; i++) {

            candidate.add(Integer.parseInt(bf.readLine()));      // 출마자 득표수
        }

        int bribeCount = 0;  // 현재 매수자 수

        while (candidate.peek() >= target) { // 가장 높은 득표수가 대상보다 낮을 떄까지 매수 반복
            bribeCount++;                   // 매수자 +1
            target++;                       // 한명 매수했으니 한표 추가
            candidate.add(candidate.poll() - 1); // 다득표자 한테 한명 빼왔으니까 한명 빼줌.

        }

        System.out.println(bribeCount);

    }
}

 

Reference

https://chanhuiseok.github.io/posts/ds-4/

 

자료구조 - 우선순위 큐(Priority Queue)와 힙(heap)

 

자료구조 - 우선순위 큐(Priority Queue)와 힙(heap)

https://nahwasa.com/entry/%EB%B0%B1%EC%A4%80-1417-%EC%9E%90%EB%B0%94-%EA%B5%AD%ED%9A%8C%EC%9D%98%EC%9B%90-%EC%84%A0%EA%B1%B0-BOJ-1417-JAVA

백준 1417 자바 - 국회의원 선거 (BOJ 1417 JAVA)