[백준 1715] 카드 정렬하기(Java)

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

이 문제는 우선순위 큐를 이용하면 쉽게 풀 수 있습니다. 문제 특성상 최소의 비교를 하기 위해선 작은 수들끼리의 합을 통한 비교가 되어야 합니다. 이 때 우선 순위 큐에 데이터가 추가되면 자동적으로 정렬이 되기 때문에 정렬로 인한 시간을 단축할 수 있습니다.

다음은 코드입니다.

import java.nio.Buffer;
import java.util.*;
import java.io.*;

public class Main{

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());

        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            pq.add(Integer.parseInt(st.nextToken()));
        }

        int res = 0;
        while(!pq.isEmpty()){
            // 첫 번째 수 뽑기
            int first = pq.poll();

            // 만약 수가 1개밖에 없었다면 그대로 종료
            if(pq.isEmpty()) break;

            // 두 번째 수 뽑기
            int second = pq.poll();

            // 두 수의 합을 다시 pq에 추가
            // 합을 결과값에 더하기
            pq.add(first+second);
            res += first+second;
        }

        System.out.println(res);
    }
}```