[1715번] 카드 정렬하기 ( 최소 힙 )

✅ 우선순위 큐

아래처럼 풀면 오답이다!
예를들어 30 40 50 60 이 있다고 가정하면 30+40 = 70 이 되고, 70장의 하나의 뭉치를 50장짜리 뭉치랑 합치는 것이 아닌 50 60 70 중에 갯수가 적은 순의 2개의 뭉치 즉 , 50 60 을 비교해서 110을 만들어서70 110 을 합치야 하기 때문이다.

따라서, 이 문제를 보면 떠올라야 하는 것이 있다. 바로, 우선순위 큐이다.
이 문제가 우선 순위 큐의 정의를 아느냐 마느냐를 묻는 것이다!
입력받은 것에서 합칠 때 마다 최소값이 필요하다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
	static long result[];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		ArrayList<Integer> A = new ArrayList<>();
		result = new long[n - 1];

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

		Collections.sort(A);
		result[0] = A.get(0) + A.get(1);

		for (int i = 1; i < n - 1; i++) {
			long sum = result[i - 1] + A.get(i + 1);
			result[i] = sum;
		}

		long min = 0;
		for (long num : result) {
			min += num;
		}

		System.out.println(min);

	}

}

✅ 코드

마지막 값은 최종 결과값이 offer 되므로 queue의 크기가 1 초과여야 한다.

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		PriorityQueue<Integer> queue = new PriorityQueue<>();
		for (int i = 0; i < n; i++) {
			queue.add(Integer.parseInt(br.readLine()));
		}

		int sum = 0;
		while (queue.size() > 1) {
			int a = queue.poll();
			int b = queue.poll();
			sum += a + b;
			queue.offer(a + b);
		}

		System.out.println(sum);
	}

}