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

문제

1715번: 카드 정렬하기

풀이

주어진 N 개의 숫자 카드를 비교할 때 최소한의 비교를 할 경우 몇 번 해야 하는지 찾는 문제 

-> 주어진 N 개의 수를 정렬하고 작은 숫자 카드 끼리 합을 구하면 된다.

 

N 개의 숫자 카드를 정렬해야 하며, 자유롭게 값을 추가하고 빼기 위해서 우선순위 큐를 사용

 

풀이 순서

1. N 개의 입력 받는 수를 우선순위 큐에 저장하고

2. 큐 사이즈가 2 이상일 때 두 개를 빼서, 합한 값을 res에 저장

3. 합한 값은 다시 큐에 넣어줌(우선순위 큐에 의해 정렬 됨)

코드

import java.io.*;
import java.util.*;

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

        int N = Integer.parseInt(br.readLine());

        for(int i = 0 ; i < N ; i ++)
            pq.offer(Integer.parseInt(br.readLine()));

        long res = 0;
        while(pq.size() > 1){
            int a = pq.poll();
            int b = pq.poll();

            res += a+b;
            pq.offer(a+b);
        }

        System.out.print(res);
    }
}