[백준] 1715 카드 정렬하기 java 쉬운 풀이 ^^ + 자주 실수하는 반례

1. 문제 설명 📌

문제 링크

이번 문제도 조건이 직관적이어서 추가적인 설명 생략

2. 접근 방식 🗃️

KEY WORD: Greedy Algorithm

Greedy 알고리즘은 매 선택의 순간에 최선의 선택을 해나가는 것이 전체 문제에서 봤을 때도 최선이라고 가정하는 알고리즘이다. 해당 문제도 최소한의 비교를 위해서는 매번 카드 수가 적은 묶음을 2개 골라서 합치면서 나아가야 한다. 그렇기에 Greedy 알고리즘을 활용해야 한다.

여기서 주의해야할 점은 합친 카드 뭉치보다 카드 수가 더 작은 기존 카드 뭉치가 2개 이상 존재할 수 있다는 것이다. 이러한 경우가 문제의 예제에는 안 나와 있어서 간과하기 쉽다. 예를 들어보자.
N = 6이고 각 카드 묶음의 카드 수는 [10, 15, 17, 19, 24, 25]라고 해보자. 처음으로 비교할 카드는 제일 작은 2개, 10과 15일 것이다. 합치면 25가 된다. 문제의 예제에서는 합친 이 수를 계속 이용해도 문제가 풀리지만, 지금의 예제에서는 다음으로 고를 두 수는 17과 19이다!
합친 카드 뭉치를 매번 비교 대상으로 상정하고 비교 상대는 주어진 카드 뭉치 중 제일 작은 것을 사용 하는 경우 비교 수는

(10 + 15) + (25 + 17) + (42 + 19) + (61 + 24) + (85 + 25) = 323 이 된다.

하지만 합친 카드 뭉치도 비교 대상에 넣어서 매번 제일 작은 카드 뭉치 2가지를 고른다면 비교 수는

(10 + 15) + (17 + 19) + (25+ 24) + (25 + 36) + (49 + 61) = 281 이 된다.

따라서 Array 정렬 이후 단순 탐색 방식이 아닌 PriorityQueue를 활용한 Greedy Algorithm을 구현해야 한다. 구현 방식은 다음과 같다.

1. 예외 처리 정의: N = 1인 경우 비교할 필요가 없으므로 0 출력, N = 2 인 경우 두 개 합해서 바로 출력
2. 초기값 설정: 오름차순 정렬 PriorityQueue에 모든 카드 묶음을 넣고, 제일 작은 값 2개를 빼내서 서로 더한다. 더한 수도 비교 대상임으로 다시 집어 넣는다.
3. 반복 : 모든 카드가 더해져서 PrirorityQueue안에 값이 1개가 남을 때까지 값을 2개 빼내서 더하고 다시 집어넣기를 반복한다.
4. 이때까지 나왔던 모든 비교횟수를 누적하여 출력한다.

3. 코드 소개 🔎

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

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> pq = new PriorityQueue<>();

        for(int i = 0; i < N; i++){
            pq.offer(Integer.parseInt(br.readLine()));
        }

        if(pq.size() == 1) {
            System.out.println(0);
            return;
        }
        int prev = pq.poll()+ pq.poll();
        pq.offer(prev);
        int acc = prev;
        while (pq.size() >= 2){
            int A = pq.poll();
            int B = pq.poll();
            int plus = A + B;
            acc += plus;
            pq.offer(plus);
        }
        System.out.println(acc);
    }
}

4. 배운 것들 🎯

반례를 생각하는 사고

내가 설명했던 주의 사항을 간과해서 문제 풀이를 많이 헤맸다. 반례를 혼자 생각해보려 했는데 떠오르지 않아, 다른 사람이 게시판에 적어놓은 반례를 보고 떠올렸다. 이렇게 확인하면서 반례를 만드는 시각을 길러야겠다.