백준 1715. 카드 정렬하기(JAVA)

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

public class Main {

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int card_case = Integer.parseInt(br.readLine());
		PriorityQueue<Integer> pq = new PriorityQueue<>();
		int result = 0;
		
		for(int i = 1 ; i <= card_case ; i++) {
			int card = Integer.parseInt(br.readLine());
			pq.add(card);
			
		}

		while(pq.size() > 1 ) {
			int num1 = pq.poll();
			int num2 = pq.poll();
			result = result + (num1 + num2);
			pq.add(num1+num2);
			
		}	
		System.out.println(result);
	}
}

모든 카드를 비교하여 최소 비교 횟수를 출력하는 문제이다. 이전에 포스팅한 우선순위 큐를 활용하여 풀 수 있는 문제이다. 먼저 연산을 쉽게 하기 위해서 오름차순으로 저장되도록 큐를 만들었다.

 처음 card_case를 3을 입력해준다. 그러면 for문을 3번 수행하면서 미리 만든 큐에 값을 저장할 수 있도록 하였다. 

↑현재 큐에 오름차순으로 정렬되어 저장되어 있는 값.

for문을 수행한 뒤 while문에 들어가면서 조건을 맞이한다. 조건의 의미는 '큐의 사이즈가 1보다 클 때까지만 while문을 수행해라'라는 것이고, 큐의 메서드인 poll()은 가장 작은 값을 출력한 뒤 큐에서 제거한다.

while(pq.size() >1){

int num1 = 10;

int num2 = 20;

30 = 0 + (10 + 20);

pq.add(30);

}

↑현재 큐에 저장되어 있는 값.

처음 while문을 수행하면 위 그림과 같이 저장되어 있다. 그리고 result는 30이라는 값을 가지고 있다. 

두 번째 while문을 수행하면 

while(pq.size() > 1){

int num1 = 30;

int num2 = 40;

100 = 30 + ( 30 + 40);

pq.add(100);

} 

↑두 번째 while문을 수행한 뒤 저장되어 있는 값

세 번째 while문을 수행하기 전에 조건을 충족하는지 검사를 해보면 현재 큐에는 100이라는 값 하나만 있어 큐의 사이즈가 1 임을 알 수 있다. 그렇기 때문에 조건을 충족하지 못하여 false가 되어 while문을 빠져나오게 된다. 

최소 비교 횟수는 100 임을 알 수 있다.