알고리즘 챌린지 5일차

문제

문제: 백준 알고리즘 1715번 카드 정렬하기

풀이

이 문제의 핵심은 묶음의 크기가 작은 카드부터 합치는 것이다.

• 작은 값부터 뽑아야 하므로 우선순위 큐를 생성해준다.
• 카드 묶음들을 우선순위 큐에 추가해준다.
• 우선순위 큐에서 두개의 값을 가져와 더한다.
• 그 값을 sum에 더해주고 우선순위 큐에 추가한다.
• 3,4과정을 우선순위 큐의 크기가 1이 될 때까지 반복해준다.
• sum을 출력한다.

코드

import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        int N = sc.nextInt();

        for (int i = 0; i < N; i++) {
            int data = sc.nextInt();
            queue.add(data);
        }

        int data1 = 0;
        int data2 = 0;
        int sum = 0;
        while (queue.size() != 1) {
            data1 = queue.remove();
            data2 = queue.remove();
            sum += data1 + data2;
            queue.add(data1 + data2);
        }
        System.out.println(sum);
    }
}

정리

이 문제는 먼저 선택된 카드 묶음이 더 많은 영향을 미치는 것을 알아차리는 것이 포인트이다. 크기가 가장 작은 카드 묶음 2개를 뽑고 이 2개를 기준으로 합친 새로운 카드 묶음을 다시 데이터에 넣고 정렬해야된다. 즉, 데이터의 삽입, 삭제, 정렬이 자주일어난다는 뜻이다. 따라서 우선순위 큐를 사용해야한다.