백준 1715, 카드 정렬하기 - Greedy

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

1. 아이디어

• n개 카드 묶음의 경우, 총 (n-1)번 합침

• 2개 카드 묶음을 합치고,
  합쳐진 카드 묶음은 또 다시 다른 카드 묶음과 합침
  => 최소 비교 횟수로 모두 합치려면, 적은 카드 묶음끼리 합쳐나가야 함
  => 각 카드 개수를 우선순위 큐에 저장 및 정렬해가면서 합침
  
  

1) PriorityQueue에 각 묶음의 카드 개수를 저장하여 정렬

• 카드 개수 적은 순으로 정렬

2) PriorityQueue에 원소가 1개 남을 때까지 다음을 반복

• 가장 작은 2개 원소를 뽑아서 더한 후, 더한 값을 다시 PriorityQueue에 추가

2. 자료구조

• PriorityQueue<Integer>: 각 카드 묶음의 카드 개수
  => 작은 순으로 정렬

3. 시간 복잡도

• PriorityQueue의 삽입/삭제 시간 복잡도: O(log_2 n)

• 2개 카드 묶음 합치기 1번
  => PQ 에서 가장 작은 2개 원소 뽑아서 더한 후, 더한 값을 PQ 에 추가
  => PQ 에서 삭제 2번 + 삽입 1번: O(3 log_2 n)

• 전체 n개 카드 묶음 합치기: 카드 합치기 (n-1)번
  => 총 시간 복잡도: O(3(n-1) log_2 n) ~= O(3n log_2 n)
  => n 최대값 대입: 3 x 10^5 x log_2 10^5 = 15 x 10^5 x log_2 10
  ~= 45 x 10^5 << 2억

코드

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

public class Main {
	static int n;				// 카드 묶음의 개수
	static PriorityQueue<Integer> pq = new PriorityQueue<>();	// 각 묶음의 카드 개수
	static int minCount;		// 출력, 최소 비교 횟수

	static void solution() {
		while (pq.size() > 1) {
			int card1 = pq.remove();
			int card2 = pq.remove();

			int mergedCard = card1 + card2;
			pq.add(mergedCard);

			minCount += mergedCard;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(
				new InputStreamReader(System.in)
		);

		n = Integer.parseInt(br.readLine());

		for (int i = 0; i < n; i++)
			pq.add(Integer.parseInt(br.readLine()));

		solution();
		System.out.println(minCount);
	}
}