카드 정렬하기

문제

백준 1715번 - 카드 정렬하기

언어

Java

순서도

우선순위 큐에 모든 데이터 넣기
우선순위 큐에서 가장 작은 두 개의 데이터를 뽑아서 더하고, 비교 횟수 갱신하고, 다시 우선순위 큐에 넣기
우선순위 큐에 데이터가 하나만 남을 때까지 위 과정 반복

문제 풀이 step 1

문제에 대한 설명은 다음과 같습니다.
정렬된 두 묶음의 숫자 카드가 있습니다. 각 묶음의 카드의 수를 A, B 라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A + B 번의 비교를 해야 합니다.
예를 들어, 20 장의 숫자 카드 묶음과 30 장의 숫자 카드 묶음을 합치려면 50 번의 비교가 필요한 것입니다.
매우 많은 숫자 카드 묶음이 책상 위에 놓여있습니다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라집니다.
이 때, 비교 횟수가 최소가 되는 경우, 비교 횟수를 구하는 문제입니다.

문제 풀이 step 2

결론부터 말하자면, 비교할 때마다 매번 가장 개수가 작은 두 개의 숫자 카드 묶음을 합치면, 정답을 구할 수 있습니다.
왜냐하면, 이전 과정에서 합친 카드를 다음 비교시 재사용되기 때문에, 최대한 재사용되는 카드 묶음의 개수를 줄여야 최소값을 구할 수 있기 때문입니다.
이를 구현하기 위해서 우선순위 큐를 사용하면 쉽게 구현할 수 있습니다.
추가 설명은 주석으로 작성하겠습니다.

후기

꼭 우선순위 큐를 구현해서 풀어볼 문제입니다.
JavaScript 는 우선순위 큐를 제공하지 않기 때문에 Java 로 풀게 되었습니다.
우선순위 큐를 이용하지 않고 푸는 방법도 있지만, 소요 시간이 상당히 오래 걸립니다.
- 저는 배열을 정렬하고, 두 개의 값을 pop 한 후에 더한 다음에 선형 비교 후에 배열에 다시 넣는 방식을 사용했지만, 시간초과가 발생했습니다.
- 어떤 분은 저와 같은 로직으로 풀었지만, 선형 비교가 아닌 이진 탐색 후에 배열에 다시 넣는 방식을 사용하셨습니다. 물론 소요 시간은 길었지만, 풀이가 상당히 신선했습니다.
- 결론적으로, 우선순위 큐를 구현해서 푸는 것이 가장 빠릅니다.

소스 코드

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

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		// 우선순위 큐 생성
		PriorityQueue<Integer> pq = new PriorityQueue<Integer>();

		int n = sc.nextInt();
		// 우선순위 큐에 모든 데이터 넣기
		for(int i = 0; i < n; i++) {
			pq.add(sc.nextInt());
		}

		int ans = 0;
		// 우선순위 큐에 데이터가 하나만 남을 떄까지 반복
		while(pq.size() > 1) {
			// 두 개의 데이터 뺀 후 더하기
			int sum = pq.remove() + pq.remove();

			// 비교 횟수 갱신
			ans += sum;

			// 우선순위 큐에 다시 넣기
			pq.add(sum);
		}

		System.out.println(ans);
	}
}