백준 1715 자바 - 카드 정렬하기

// 카드 정렬하기
package Gold_IV_4;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

public class Ex1715 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PriorityQueue<Integer> cards = new PriorityQueue<>();

        int n = Integer.parseInt(br.readLine()); // 카드 묶음 카드 수

        for (int i = 0; i < n; i++) {
            cards.add(Integer.parseInt(br.readLine())); // 묶음당 장 수 저장 및 오름차순 정렬
        }

        int sum = 0; // 비교 횟수 저장
        while (cards.size() > 1) { // 카드 묶음이 하나면, 비교 X
            int a = cards.poll();
            int b = cards.poll();
            cards.add(a + b);

            sum += a + b;
        }

        System.out.println(sum);
    }
}

 

문제

1715번: 카드 정렬하기 (acmicpc.net)

 

풀이

이번 문제는 알고리즘 분류에 우선순위 큐가 있고 문제 예시에서 가장 작은 수끼리 더하는 것을 보고 이렇게 하면 되지 않을까 하면서 했는데 됐다.

핵심은 PriorityQueue(우선순위 큐)를 사용하는 거였다. 그 외에는 코드 자체는 복잡한 내용이 없어서 딱히 설명할게 없다.