1715번 카드 정렬하기(Java)

 우선순위 큐 알고리즘 문제

 

 우선순위 큐를 이용하면 금방 풀 수 있다.

 

 ex) 3 3 3 3

   1) 우선 두 개를 빼내서 더한다. (3+3=6)

   2) 큐 안에 넣는다. (3 3 6)

   3) 다시 두 개를 빼내서 더한다. (3+3=6)

   4) 큐안에 넣는다. (6 6)

   5) 다시 두 개를 빼내서 더한다. (6+6=12)

   6) 이 때 큐 안에 남은 값들이 없으므로 종료한다.

   7) 두 값을 꺼내 더한 값들을 더한다. (6+6+12=24)

   

 만약 1개의 값이 들어왔다면 비교할 대상이 없으므로 횟수는 0번이다.

 

package algorithm;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
 
public class Problem1715 {
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        
        for(int i=0;i<N;i++) {
            priorityQueue.add(Integer.parseInt(br.readLine()));
        }
        
        /*
         * while(!priorityQueue.isEmpty()) { int x = priorityQueue.poll(); }
         */
        solved(priorityQueue);
    }
    
    public static void solved(PriorityQueue<Integer> priorityQueue) {
        
        int sum=0;
 
        while(!priorityQueue.isEmpty()) {
            
            if(priorityQueue.size()>1) {
                int x = priorityQueue.poll();
                int y = priorityQueue.poll();
 
                sum+=(x+y);
 
                if(!priorityQueue.isEmpty()) {
                    priorityQueue.add(x+y);
                }
            }
            else {
                break;
            }
        }
        
        System.out.println(sum);
    }
 
}