[Java] 백준(골드-4) 1715번 - 카드 정렬하기

문제 풀이

---

이 문제는 우선순위 큐를 활용해 풀 수 있는 문제 중 하나이다.

아이디어 도출

먼저 카드뭉치를 비교하기 위해서는 두 수의 합을 구하고 비교해야 한다. 문제의 예제 테스트케이스를 보면 (10+20) + (30 + 40) = 100 처럼, 앞의 두 수를 더한 값을 뒤의 수와 합해가야 한다.

이로 인해, 카드 수를 더해가는 연산마다 가장 작은 값을 누적시켜야 한다는 것을 알 수 있다. 이때, 왜 우선순위 큐를 사용해야 하는 걸까?

두 수를 더하고 큐에 다시 삽입해가는 것은 동일하지만, 단순히 기본 큐를 사용하게 되면 맨 뒤로 삽입되는 값이 있기에 연산에 바로 사용할 수 없다. 우선순위 큐는 낮은 숫자부터 꺼낼 수 있다는 특징을 가지기에 큐가 아닌 우선순위 큐를 이용해 가장 작은 값의 합을 누적시킬 수 있게 된다.

최소한의 비교를 하기 위해서는 낮은 값부터 먼저 더해야 하므로 오름차순으로 정렬된 상태에서 값을 더하기 위해 우선순위 큐를 사용해야 한다. 여기서 오름차순으로 정렬된 상태라는 것은 우선순위 큐에서는 낮은 수부터 꺼내오며 덧셈할 수 있다는 의미이다.

우선순위 큐를 이용해 문제 해결을 위한 아이디어는 다음과 같다.

1. while문을 사용하여 더한 값을 계속해서 우선순위 큐에 넣어준다.
2. 우선순위 큐의 원소가 1개만 남았다면 더 이상 더할 수가 없다는 것으로 간주하고 연산을 종료한다.

또한, 문제 풀이시 자료형과 관련하여 고려해야 할 점은 다음과 같다.

최악의 경우 100,000개의 N이 주어지는데 1~100000을 다 더해도 int 범위를 초과하기 때문에 long을 사용해야 한다.

문제 풀이를 위해 작성한 코드는 아래와 같다.

작성코드

---

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

class Main {    

    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int N = Integer.parseInt(br.readLine());
        PriorityQueue<Long> pq = new PriorityQueue<>();

        for(int i=0; i<N; i++) {
            pq.offer(Long.parseLong(br.readLine()));
        }
        
        // N의 범위가 최대 100,000이기 때문에 int형이 아닌 long형을 사용한다.
        long result = 0;

        // 우선순위 큐의 원소가 2개 이상 있어야 비교할 수 있다.
        while(pq.size() > 1) {
            // 우선순위가 높은 낮은 숫자부터 우선순위 큐에서 2개를 꺼낸다.
            long now = pq.poll();
            long next = pq.poll();
            
            // 두 수를 더해주고 더한 수를 result에 더해간다.
            long sum = now + next;
            result += sum;
            
            // 두수를 더한 수를 우선순위 큐 마지막에 삽입한다.
            pq.offer(sum);
        }

        bw.write(result+"\n");
        
        bw.close();
        br.close();
    }

}

출처

---

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.