[BaekJoon] 1715 카드 정렬하기 (Java)

1.  문제 링크

https://www.acmicpc.net/problem/1715

2.  문제

요약

• 정렬된 두 묶음의 숫자 카드가 있는데, 각 묶음의 카드의 수를 A, B라고 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A + B 번의 비교를 해야 합니다.
• 매우 많은 숫자 카드 묶음이 책상 위에 놓여 있고 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라 비교 횟수가 매우 달라집니다.
• N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지를 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 100,000보다 작거나 같은 N이 주어지고 두 번째 줄부터 N개의 줄에는 1,000보다 작거나 같은 양의 정수인 숫자 카드 묶음의 각각의 크기가 주어집니다.
• 출력: 첫 번째 줄에 최소 비교 횟수를 출력합니다.

3.  소스코드

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

public class Main {
	static int N, result;
	static PriorityQueue<Integer> card_num;
	static void input() {
		Reader scanner = new Reader();
		N = scanner.nextInt();
		card_num = new PriorityQueue<Integer>();
		result = 0;
		for(int i = 0; i < N; i++) {
			card_num.offer(scanner.nextInt());
		}
	}
	
	static void solution() {
		while(card_num.size() > 1) {
			int card1 = card_num.poll();
			int card2 = card_num.poll();
			card_num.offer(card1 + card2);
			result += card1 + card2;
		}
		System.out.println(result);
	}
	
	public static void main(String[] args) {
		input();
		solution();
	}
		
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
}

4.  접근

• 카드 묶음 수가 적은 순서대로 두 개씩 묶어서 비교하면 비교 횟수를 최소로 만들 수 있습니다.
• 그렇기 때문에 PriorityQueue에 주어진 카드 묶음 개수들을 넣고 PriorityQueue에서 2개씩 빼서 그 2개의 카드 묶음을 비교한 후에 그 수를 다시 PriorityQueue에 넣어주는 작업을 PriorityQueue에 수가 한 개 남을 때까지 진행합니다.
• PriorityQueue에 수가 한 개 남았다는 것은 주어진 모든 카드 묶음에 대해서 비교를 마치고 하나의 카드 묶음이 되었다는 의미이므로 이 값이 문제의 답이 됩니다.