[백준 Baekjoon] 1715번 카드 정렬하기 - JAVA

백준 Baekjoon 1715번 카드 정렬하기 - JAVA

---

문제 풀이

문제의 예시에서 처럼 최소한의 비교를 위해서는 매번 가장 작은 2개의 묶음을 비교하면 된다. 매번 가장 작은 묶음을 쉽게 찾아 꺼내기 위해 우선순위 큐를 사용한다. 묶음이 1개만 남을때까지 가장 작은 두 개의 묶음을 꺼내 더한값을 총 비교횟수에 더하고 우선순위 큐에 넣어준다. while문이 종료되면 총 최소 비교 횟수가 남게 되고 출력하면 된다.

카드 묶음의 크기는 1000으로 작으나 모든 카트 묶음이 1000이라 하고 N이 100,000인 경우에는 int값의 범위를 초과하기 때문에 우선순위 큐와 총 비교 횟수는 long 타입을 사용해야 한다.

소스 코드

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<Long> pq = new PriorityQueue<>();
        for (int i = 0; i < N; i++) {
            pq.add(Long.parseLong(br.readLine()));
        }

        long answer = 0;

        while (pq.size() >= 2) {
            long a = pq.poll();
            long b = pq.poll();

            answer += a + b;
            pq.add(a + b);
        }

        System.out.println(answer);
    }
}