백준 1715번 카드 정렬하기

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

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

        long answer = 0;
        for (int i = 0; i < N-1; i++) {
            int A = pq.poll();
            int B = pq.poll();
            pq.add(A+B);
            answer += A+B;

        }
        System.out.println(answer);

    }
}

풀이방법

1. 카드를 오름차순 정렬하고, 앞에 두 묶음을 더한다.
2. 더한 카드를 새로운 한 묶음으로 하여, 카드 묶음들을 재정렬한다.
3. 이를 계속 반복한다.

👉즉, 앞에 두개 더하고, list 정렬, 앞에 두개 더하고, list 정렬을 반복한다.
왜냐면, 가장 작은 카드 묶음들을 더해야 최소값을 가지기 때문이다.
하지만, 매번 더하고, 정렬하면, 시간초과가 발생한다.

📢따라서 매번 정렬할 필요없이 가장 작은 카드 묶음을 찾을 수 있는 우선 순위 큐를 사용한다.
A,B에 가장 작은 두 값이 poll()되므로, 매번 오름차순으로 정렬할 필요가 없다.

🔉우선순위 큐의 기본 우선순위는 최소 힙 방식으로 구현된다.
따라서 우선순위 큐 내에 숫자는 최솟값이 가장 높은 우선순위를 가진다.
만약 최대 힙 방식으로 구현해서 최댓값이 가장 높은 우선순위를 가지려면,
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); 로 구현 할 수 있다.

후기

이 문제의 핵심은 for문을 돌며 매번 정렬해서, 최솟값 두개를 찾는 규칙과
이를 매번 정렬하지 않고, 우선순위 큐를 사용해서 시간 복잡도를 줄이는것이 핵심이다.

우선순위 큐에 대해서는 이번에 새로 알게 되어 의미있었고, 규칙자체는 찾아서 구현할 수 있어서, 반은 풀었다고 할 수 있다.ㅋ