/ BOJ

BOJ_1417_국회의원선거_JAVA

문제 : 국회의원선거

링크 : BOJ_1417_국회의원선거

접근 방식

배열의 최댓값을 구하면서 인덱스 값을 같이 저장한다. 다솜의 번호는 가장 첫 번째이므로, 최댓값의 인덱스가 첫 번째 번호라면 투표를 뺏어올 필요가 없으니 0이다.

그렇지 않은 경우라면, 배열의 최댓값에서 투표 수를 1 꺼내서 다솜의 투표에 추가하면 된다.

문제는 최댓값이 다솜과 같은 인원이 다수 있을 때인데, 이 상황에서는, 최대 투표값을 크거나 같은 것으로 설정하면 해결된다. 그 이유는 다솜은 무조건 첫 번째 후보이기 때문에, 자신과 같은 투표수의 뒷 후보가 있다면 자동으로 본인은 최대 득표자에서 벗어나게 된다.

풀이 방법

  1. 선거의 총 참여 인원수를 읽어와 저장하고, 각 후보의 투표 수를 N개 크기의 배열에 저장한다.

  2. 다솜의 투표 수가 최대가 될때까지 반복하는 반복문을 돌린다.

  3. 배열을 순회하며 최대 득표자를 찾고, 만약 최댓값이 다솜이라면 반복문을 나간다.

  4. 다솜이 최대 득표자가 아니라면, 최대 득표 후보는 -1을 다솜은 +1을 시켜준다.

  5. 반복문이 한 번 돌아갈 때마다 카운트를 1 증가시킨다.

  6. 모든 반복이 종료된 후 카운트 값을 출력한다.

소스 코드


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

public class BOJ_1417_국회의원선거 {
	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(in.readLine());

		int arr[] = new int[N];

		for(int i=0;i<N;i++) {
			arr[i] = Integer.parseInt(in.readLine());
		}
		int cnt = 0;
		// 다솜이 최댓값이 될때까지 반복
		while(true) {
			int max = 0;
			int maxIndex = 0;
			for(int i=0;i<N;i++) {
				// 표 중에 최댓값을 구한다. index도 같이 저장한다.
				if(max <= arr[i]) {
					max = arr[i];
					maxIndex = i;
				}
			}
			// 최댓값이 다솜이라면
			if(maxIndex == 0) {
				break;
			}
			arr[maxIndex]--;
			arr[0]++;
			cnt++;
		}

		System.out.println(cnt);
	}
}