[백준 1715] 카드정렬하기

🫡 문제

백준 1715 - 카드정렬하기

🫡 코드

import java.util.PriorityQueue;
import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		
		//작은 값들을 정렬시키기 위해 우선순위 큐 사용
		PriorityQueue<Integer> que = new PriorityQueue<Integer>();
		
		for(int i=0; i<N; i++) {
			int num = sc.nextInt();
			que.add(num);
		}
		
		int num1 = 0;
		int num2 = 0;
		int sum = 0;
		
		while(que.size()!=1) { //큐의 크기가 1보다 작으면 더이상 더할 값이 없음
			num1 = que.remove();
			num2 = que.remove();
			sum += num1+num2;
			que.add(num1+num2);
		}
		
		System.out.println(sum);
		
	}
}

🫡 풀이

N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지를 구하는 문제

정렬된 두 묶음의 숫자 카드를 A,B라고 하면 보통 두 묶음을 합쳐서 하나로 만드는데 A+B번의 비교를 해야한다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다.

일단 작은 카드끼리 먼저 합해주는 것이 비교횟수를 줄일 수 있기 때문에 작은 것끼리 더해주고 정렬해주고 더해주고 정렬해주는 행위를 반복을 해야한다. 그래서 Queue 를 사용해주었고 작은 값들을 순서대로 정렬해주는 PriorityQueue가 있다고 하길래 사용해주었다.

Queue
|40 20 10|
20 + 10 = 30 (작은 값을 더해서 queue에 다시 add - 반복)
|40 30|
40 + 30 = 70
|70|