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

문제 : boj1417

 

1. 시뮬레이션을 돌리자!

  이 문제를 만족시키기 위해서 어떻게 해야할지부터 생각해보자. 다솜이가 처음 얻은 듣표수를 a라고 하겠다. 그럼 그 나머지 득표수들을 -시키면서, a를 +시켜나갈 때 나머지 득표수 중 가장 큰 득표수보다 a가 커지면 된다.

 

  그렇다면 중요한 요소는 나머지 득표수 중 가장 큰 득표수이다. 이걸 max라 하겠다. 결국 매번 max값을 -1 시키고, a를 +1 시켜나가면 원하는 답을 구할 수 있다. 예를들어 다음의 경우를 보자.

4
1
3
3
4

  답을 찾는 과정은 다음과 같다. 매번 max값을 찾고(빨간색으로 나타냈다), 해당 값을 -1 시키고 a를 +1 시킨다. 그러다가 max<a이면 답을 출력하면 된다!

  위와 같이 배열에 값들을 두고 매번 max값을 찾거나 정렬하면서 진행하면 된다. 즉 시뮬레이션을 돌리는 것이다. 이 경우 시간복잡도는 대략 O(N^2) 정도 된다(정렬시엔 O(N^2logN). 사실 총 득표수 합에 비례하긴 하지만 어차피 제한이 적어 크게 차이 안나므로 대강 N으로 나타냈다.). 애초에 제한이 아주 작아서 이렇게 해도 매우 빠른 시간 안에 찾을 수 있다.

 

  이렇게 짠 코드는 다음과 같다.

O(N^2logN) 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        if (n == 1) {
            System.out.println(0);
            return;
        }
        int a = Integer.parseInt(br.readLine());
        int[] arr = new int[n-1];
        for (int i = 0; i < n-1; i++) arr[i] = Integer.parseInt(br.readLine());
        int cnt = 0;
        while (true) {
            Arrays.sort(arr);
            if (arr[n-2] < a) break;
            cnt++;
            arr[n-2]--;
            a++;
        }
        System.out.println(cnt);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}

 

 

2. '1'로도 충분하긴 하지만, 제한이 커졌다고 생각하고 효율성을 더 좋게 해보자!

  이 경우 간단하게 최대 힙을 사용하면 좀 더 효율적으로 짤 수 있다. 이 경우 max 값을 찾을 때 O(logN)으로 가능하다. 따라서 총 O(NlogN)의 효율성을 가진다.

 

 

코드 : github

O(NlogN) 코드

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

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int a = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        while (n-->1) pq.add(Integer.parseInt(br.readLine()));
        int cnt = 0;
        while (!pq.isEmpty() && pq.peek() >= a) {
            cnt++;
            a++;
            pq.add(pq.poll()-1);
        }
        System.out.println(cnt);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}