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

🔗 문제 링크

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

👨🏻‍💻 작성한 코드

import java.io.*;
import java.util.PriorityQueue;

public class Main {

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PriorityQueue<Integer> queue = new PriorityQueue<>();
		
		int result = 0;
		
		int n = Integer.parseInt(br.readLine());
		
		for (int i=0; i<n; i++) {
			queue.offer(Integer.parseInt(br.readLine()));
		}
		
		while (queue.size()!=1) {
			int n1 = queue.poll();
			int n2 = queue.poll();
			
			result += (n1+n2);
			
			
			queue.offer(n1+n2);
		}
		
		System.out.println(result);
	}

}

📝 정리

이번 문제의 경우 카드 묶음을 두개씩 묶어가며 최종적으로 하나의 카드묶음으로 만드는데 그때의 비교가 가장 적을 때의 비교 횟수를 구하는 문제이다.

카드 묶음을 합칠 때의 비교 횟수는 각각의 카드 묶음의 장수를 더한 만큼이 되며 이를 최소로 하기 위해서는 최소 heap인 PriorityQueue를 사용하여 문제를 풀었다.