[백준 / Java] 1715번 카드 정렬하기

문제 링크 : https://www.acmicpc.net/problem/1715

1715번: 카드 정렬하기

 

 

이번 포스팅에서는 백준 골드 4문제인 카드 정렬하기 문제를 우선순위 큐(Priority Queue)를 사용하여 해결한 방법에 대해 공유하려고 합니다.

골드 4 난이도의 문제라 어려워 보일 수도 있지만, 우선순위 큐에 대해서 알고 있다면 쉽게 풀 수 있는 문제였습니다.

저는 대신 문제를 이해하는데 시간이 조금 걸렸는데요. 문제 개요와 해결 방법, 그리고 우선순위 큐가 무엇인지 알게 된 내용을 공유해 보겠습니다.

 

 

우선순위 큐(Priority Queue)란?

우선순위 큐는 자료구조의 한 종류로, 각 요소가 특정 우선순위를 가지며 그 우선순위에 따라 요소들이 처리되는 방식을 따릅니다. 일반적으로 큐는 선입선출(FIFO, First In First Out)의 특성을 가지며, 들어온 순서대로 데이터를 처리합니다. 그러나 우선순위 큐는 이와 다르게, 우선순위가 높은 요소가 먼저 처리되는 방식으로 동작합니다. 이 말은 들어온 순서보다 요소의 중요도에 따라 처리 순서가 결정된다는 뜻입니다.

 

우선순위 큐는 내부적으로 힙(Heap) 자료구조를 사용하여 구현됩니다. 힙은 트리의 한 종류로, 특정 규칙에 따라 부모와 자식 노드가 정렬됩니다. 예를 들어, 최소 힙(min-heap)에서는 부모 노드의 값이 자식 노드의 값보다 작거나 같도록 정렬됩니다. 이렇게 함으로써 최솟값이 항상 트리의 루트에 위치하게 되어, 우선순위 큐에서 가장 작은 값을 빠르게 찾아낼 수 있는 것입니다. 반대로 최대 힙(max-heap)에서는 부모 노드의 값이 자식 노드보다 크거나 같아 최댓값이 루트에 위치하게 됩니다.

 

일반적인 큐와 우선순위 큐의 가장 큰 차이점은 처리 순서의 기준입니다. 일반 큐에서는 먼저 들어온 데이터가 먼저 나가지만, 우선순위 큐에서는 우선순위가 높은 데이터가 먼저 나갑니다.

 

주요 메서드

• `poll()` : 큐에서 가장 우선순위가 높은 요소를 제거하고 반환합니다.
• `peek()` : 가장 우선순위가 높은 요소를 제거하지 않고 반환합니다.
• `add()` : 요소를 큐에 추가합니다.
• `offer()` : 요소를 큐에 추가합니다. `add()`와 비슷하지만, 큐에 여유 공간이 없을 때 예외 대신 false를 반환합니다.

 

 

문제 개요

이 문제는 그리디(greedy) 알고리즘을 사용하는 문제입니다. 그리디 알고리즘은 현재 상황에서 가장 최적인 선택을 하는 알고리즘으로, 이 문제에서는 매번 가장 작은 두 카드 묶음을 합치는 것이 전체 비용을 최소화하는 최적의 방법입니다.

 

문제 예시

예시 이미지를 기준으로 카드 묶음이 `[10, 20, 40, 50]`이라고 가정했을 때, 다음과 같은 방식으로 문제를 해결할 수 있습니다.

1. 먼저 가장 작은 두 묶음 `[10, 20]`을 꺼내 합칩니다. 합친 묶음 `[30]`을 다시 큐에 넣으면 큐에는 `[30, 40, 50]`이 남습니다.
2. 다시 가장 작은 두 묶음 `[30, 40]`을 꺼내 합칩니다. 합친 묶음 `[70]`을 다시 큐에 넣으면 큐에는 `[50, 70]`이 남습니다. 이때 우선순위 큐는 순서가 있는 자료구조 이기 때문에 `[70, 50]`이 아니라 `[50, 70]`으로 정렬이 됩니다.
3. 마지막으로 남은 두 묶음 `[50, 70]`을 합치면 `[120]` 하나의 묶음이 남게 됩니다.

 

총 비용을 계산해 보면

• 첫 번째 합칠 때 비용: `30`
• 두 번째 합칠 때 비용: `70`
• 세 번째 합칠 때 비용: `120`

 

따라서, 총 비용은 `30 + 70 + 120 = 220`입니다.

 

 

접근 방법

저는 아래와 같은 순서로 접근하였습니다.

1. 우선순위 큐에 각 카드 묶음의 크기를 삽입합니다.
2. 큐에서 가장 작은 두 묶음을 꺼내 더한 후, 다시 큐에 삽입합니다.
3. 큐에 하나의 묶음만 남을 때까지 이를 반복합니다.

 

 

최종 코드

 

import java.io.*;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static PriorityQueue<Integer> pq = new PriorityQueue<>();
    static int N;
    static int answer;

    public static void main(String[] args) throws IOException {
        // 입력 및 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        
        // 카드 묶음을 우선순위 큐에 추가
        for(int i = 0; i < N; i++) {
            pq.add(Integer.parseInt(br.readLine()));
        }
        
        // 카드 묶음 합치기
        while(pq.size() >= 2) {
            int a = pq.poll();  // 가장 작은 묶음
            int b = pq.poll();  // 두 번째로 작은 묶음
            answer += a + b;    // 비용 누적
            pq.offer(a + b);    // 합친 묶음을 다시 큐에 추가
        }
        
        // 결과 출력
        bw.write(String.valueOf(answer));
        bw.close();
        br.close();
    }
}

 

 

마치며

이번 문제는 우선순위 큐를 알고 있다면 쉽게 풀 수 있는 문제였습니다.

이전에 풀었던 '백준 7662번 이중 우선순위 큐' 문제 덕분에 이번에도 우선순위 큐의 사용에 익숙하게 접근할 수 있었고, 20-30분 정도의 시간이 소요되었습니다. 하지만 그리디 알고리즘의 경우 DFS/BFS처럼 명확한 패턴이 있는 것이 아니라 문제마다 다르게 접근해야 한다는 점에서 다양한 문제를 경험하는 것이 중요하다는 것을 다시 한번 깨달았습니다.