백준 1417번 국회의원 선거

문제

다솜이는 사람의 마음을 읽을 수 있는 기계를 가지고 있다. 
다솜이는 이 기계를 이용해서 2008년 4월 9일 국회의원 선거를 조작하려고 한다.
다솜이의 기계는 각 사람들이 누구를 찍을 지 미리 읽을 수 있다. 
어떤 사람이 누구를 찍을 지 정했으면, 반드시 선거때 그 사람을 찍는다.
현재 형택구에 나온 국회의원 후보는 N명이다. 
다솜이는 이 기계를 이용해서 그 마을의 주민 M명의 마음을 모두 읽었다.
다솜이는 기호 1번이다. 
다솜이는 사람들의 마음을 읽어서 자신을 찍지 않으려는 사람을 돈으로 매수해서 
국회의원에 당선이 되게 하려고 한다. 
다른 모든 사람의 득표수 보다 많은 득표수를 가질 때, 그 사람이 국회의원에 당선된다.
예를 들어서, 마음을 읽은 결과 기호 1번이 5표, 기호 2번이 7표, 기호 3번이 7표 라고 한다면, 
다솜이는 2번 후보를 찍으려고 하던 사람 1명과, 3번 후보를 찍으려고 하던 사람 1명을 돈으로 매수하면,
국회의원에 당선이 된다.

돈으로 매수한 사람은 반드시 다솜이를 찍는다고 가정한다.

다솜이가 매수해야하는 사람의 최솟값을 출력하는 프로그램을 작성해라

 

입력

첫째 줄에 후보의 수 N

둘째 줄부터 차례대로 기호 1번을 찍으려고 하는 사람의 수, 기호 2번을 찍으려고 하는 수, 
이렇게 총 N개의 줄에 걸쳐 입력

출력

첫째 줄에 다솜이가 매수해야 하는 사람의 최솟값을 출력

 

풀이

 

이문제를 풀이하는데 우선순위 큐를 사용해보려 한다

일반적인 큐의 구조 FIFO(First In First Out)를 가지면서, 
데이터가 들어온 순서대로 데이터가 나가는 것이 아닌 우선순위를 먼저 결정하고 
그 우선순위가 높은 데이터가 먼저 나가는 자료구조

 

쉽게 말하면 사용자가 내림차순, 혹은 오름차순으로 정렬을 한다 정하면

따로 정렬을 해주지 않아도 자동적으로 정렬이 된다는 뜻이다

        	// 낮은 숫자 우선인 우선순위 큐
		PriorityQueue<Integer> pq = new PriorityQueue<>();
		pq.add(1000);
		pq.add(10);
		pq.add(100);
		System.out.println(pq.toString());
		// 결과값 [10, 1000, 100]
        
        
		// 높은 숫자 우선인 우선순위 큐
		PriorityQueue<Integer> pq2 = new PriorityQueue<>(Collections.reverseOrder());
		pq2.add(1);
		pq2.add(10);
		pq2.add(100);
		
		System.out.println(pq2.toString());'
        	// 결과값 [100, 1, 10]

 

 

이와같이 우선순위를 정해 차례대로 처리를 하는것이 우선순위 큐 알고리즘이다

 

문제를 보면 5, 7, 7과 같은 입력이 있었을 때 출력값은 2였다

첫번째 숫자가 두번째, 세번째 숫자보다 커져야 한다면 

5 7 7  >>  + 1
6 6 7  >>  + 1
7 6 6  >>  2

위 의 과정을 거친다 할 수 있다

 

우선순위 큐 사용법

// 첫번째 값을 반환하고 제거 비어있다면 null
priorityQueueLowest.poll();

// 첫번째 값 제거 비어있다면 예외 발생
priorityQueueLowest.remove(); 

// 첫번째 값을 반환만 하고 제거 하지는 않는다.
// 큐가 비어있다면 null을 반환
priorityQueueLowest.peek();

// 첫번째 값을 반환만 하고 제거 하지는 않는다.
// 큐가 비어있다면 예외 발생
priorityQueueLowest.element();

// 초기화
priorityQueueLowest.clear();

 

 

이 문제에서 중요한것은 하나다

• 첫번째 숫자가 제일 커질때 까지입력한 수 중 제일 큰수에서 하나씩 빼 첫번째 숫자에 더해준다

여기서 우선순위 큐가 유효하게 작용한다

아래와 같은 과정을 거치면 해결할 수 있을것이라 생각한다

1. 첫번째 숫자를 제외한 나머지 숫자를 배열에 넣고
2. 첫번째 숫자와 내림차순 우선순위 큐를 적용한 배열의 0번째 인덱스값을 비교해
3. 크면 -1

코드

import java.util.*;

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt(); // 후보자 수
		int count = 0; // 뺄때마다 카운트
		
		int dasom = sc.nextInt(); // 나머지 후보자와 다솜을 비교하기 위해 다솜 따로 구분
		
		if (N==1) {  // 후보자가 다솜 하나면 0 출력하고 바로 종료
			System.out.println(0);
			return;
		}
		else {
			PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
			
			for(int i= 1; i<N; i++) { // 나머지 후보자 입력
				pq.add(sc.nextInt());
			}
			
			while (pq.peek() >= dasom) { // dasom의 표가 큐 안의 최고값보다 많을때까지
				int maxVote = pq.poll(); // maxVote 변수에 큐 안의 최고값 넣고 제거
				pq.add(maxVote -1); // 최고값에서 -1 한 값을 다시 큐안에 삽입
				dasom ++; // 다솜표 + 1;
				count ++; // 카운트 + 1;
			}
		}
		System.out.println(count);
	}
}

결과

 

후기

처음에는 후보자가 한명일 때의 경우를 생각하지 않아

큐가 비어있다는 오류 메시지를 발생시켰다

 

그래서 

if (N==1) {  // 후보자가 다솜 하나면 0 출력하고 바로 종료
			System.out.println(0);
			return;
		}
		else {

조건문을 사용해 N이 1이면 0을 출력하고 바로 종료하도록 했고

아니면 큐에 값을 넣는것으로 진행되게 수정했다