[코딩테스트] 백준 1715 자바

백준 1715

백준 1715 문제

해당 문제는 카드 묶음의 카드의 개수가 작은 순서대로 먼저 합치는 것이 전체 비교 횟수를 줄일 수 있는 방법이다.

현재 데이터 중 가장 작은 카드의 개수를 가진 묶음 2개를 뽑아야 하고, 이 2개를 합친 새로운 카드 묶음을 다시 데이터에 넣고 정렬해야 한다.

즉, 데이터의 삽입, 삭제, 정렬이 자주 일어난다. 따라서 이 문제는 우선순위 큐를 이용해서 풀어야 한다.

import java.util.*;

public class Boj1715 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 카드 묶음 개수
        PriorityQueue<Integer> queue = new PriorityQueue<>(); // 우선순위 큐 선언
        int sum = 0; // 누적된 비교 횟수

        for (int i = 0; i < n; i++) { // n만큼 반복
            queue.offer(sc.nextInt()); // 우선순위 큐에 데이터 저장
        }

        while (queue.size() != 1) { // 우선순위 큐 크기가 1이 될 때까지 반복
            // 2개의 카드 묶음을 큐에서 뽑음
            int data1 = queue.poll();
            int date2 = queue.poll();

            sum += data1 + date2; // 2개 카드 묶음을 합치는 데 필요한 비교 횟수를 sum에 더함
            queue.offer(data1 + date2); // 2개 카드 묶음의 합을 우선순위 큐에 다시 넣음
        }

        System.out.println(sum); // 누적된 비교 횟수 출력
    }
}

문제 풀이

1. 카드 묶음 개수 n을 입력받아 저장한다.
2. 우선순위 큐 queue를 선언한다.
3. 누적 된 비교 횟수 sum을 0으로 초기화한다.
4. n만큼 반복하면서 입력 받은 데이터를 우선순위 큐 queue에 저장한다.
5. 우선순위 큐 queue 사이즈가 1이 될 때까지 아래 과정을 반복한다.
   1. queue에서 카드 묶음을 하나 꺼내서 data1에 저장한다.
   2. queue에서 다른 카드 묶음 하나를 더 꺼내서 data2에 저장한다.
   3. data1와 data2의 합을 sum에 더한다.
   4. data1와 data2의 합을 queue에 넣는다.
6. queue 사이즈가 1이 되면 sum을 출력한다.