[백준] 1417번: 국회의원 선거 (실버5, 구현자료, 구조그리디, 알고리즘시뮬레이션, 우선순위 큐, JAVA)

 

문제 링크 : https://www.acmicpc.net/problem/1417

 

1417번: 국회의원 선거 (실버5, 구현자료, 구조그리디, 알고리즘시뮬레이션, 우선순위 큐, JAVA)

매수해야하는 사람의 수를 구하는 문제인데, 예제의 경우 다솜(5)이가 2번과 3번의 사람을 한명씩 매수하게 되면 득표 수가 7,6,6이 되므로 두명을 매수해야하기 때문에 출력값은 2가 나와야 합니다.

 

아래의 코드에서 각각의 값을 입력받고, 한명의 후보밖에 없을 경우(입력되는 값이 1일 때) 0을 출력합니다.

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[] numbers = new int[N];
        int maxValue = 0;
        int count = 0;
        int maxIndex = 0;
        for(int i=0; i<N; i++) {
           numbers[i] = Integer.parseInt(br.readLine());
        }
        
        if(N==1) {
           System.out.println("0");
        }
	}
}

 

그 후 while문을 작성하는데, N이 1보다 클 경우 라는 조건식을 주고 나서 입력받은 숫자 중 가장 큰 값과 현재 값의 인덱스를 저장합니다. 그 후 numbers[0] (다솜)이 maxValue보다 클 경우 count를 출력하며 while문을 중지하고, 작거나 같을 경우 다솜이의 값을 1 증가, 가장 큰 값이였던 인덱스에 들어있는 값과 maxValue를 1 감소하며 count를 증가 시킵니다.

        while(N>1) {
           
           for(int i=1; i<N; i++) {
               if(numbers[i] > maxValue) {
                  maxValue = numbers[i];
                  maxIndex = i;
               }
            }
           
           if(numbers[0] > maxValue) {
              System.out.println(count);
              break;
           } else if(numbers[0] <= maxValue) {
              numbers[0]++;
              numbers[maxIndex]--;
              maxValue--;
              count++;
           } 
        }

 

전체 코드는 아래와 같습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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[] numbers = new int[N];
        int maxValue = 0;
        int count = 0;
        int maxIndex = 0;
        for(int i=0; i<N; i++) {
           numbers[i] = Integer.parseInt(br.readLine());
        }
        
        if(N==1) {
           System.out.println("0");
        }
        
        while(N>1) {
           
           for(int i=1; i<N; i++) {
               if(numbers[i] > maxValue) {
                  maxValue = numbers[i];
                  maxIndex = i;
               }
            }
           
           if(numbers[0] > maxValue) {
              System.out.println(count);
              break;
           } else if(numbers[0] <= maxValue) {
              numbers[0]++;
              numbers[maxIndex]--;
              maxValue--;
              count++;
           } 
        }
   }
}