처음에 이 문제 보고 골드다 !! 이런 다음에 뭔가 정렬인데 골드에 있으면 일반 순차 탐색이 아닌 퀵 정렬을 사용해야 하나 싶어서 직접 구현 까지 했는데.....

풀이는 간단한 우선선위 큐였다니........... 충격쓰............

📕 우선순위 큐

이진트리 힙으로 구성이 되어있다. 따라서 add, poll 등 추가 또는 삭제 시 O(logN)시간이 걸린다.

📜 Priority Queue 선언하기

우선순위가 높은 순, 낮은 순

PriorityQueue<Integer> priorityQueue1 = new PriorityQueue<>();
PriorityQueue<Integer> priorityQueue2 = new PriorityQueue<>(Collections.reverseOrder());
PriorityQueue<String> priorityQueue3 = new PriorityQueue<>();
PriorityQueue<String> priorityQueue4 = new PriorityQueue<>(Collections.reverseOrder());	

📜 Priority Queue 값 추가하기

add(), offer() 메서드

• 입력한 순서로 들어가는 것이 아니라, 우선 순위 큐만의 정렬방식으로 정렬!

📜 Priority Queue 값 삭제하기

poll(), remove() 메서드를 사용하면 우선순위가 가장 높은 값을 제거
remove(int Index) 메서드를 사용하면 Index 순위에 해당하는 값을 제거

📜 Priority Queue 크기 구하기

size() 메서드

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

public class Main {

    public static int N, answer;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int i = 0; i < N; i++) pq.offer(Integer.parseInt(br.readLine()));
        
        while (pq.size() != 1) {
            int one = pq.poll();
            int two = pq.poll();
            
            int sum = one + two;
            
            answer += sum;
            pq.offer(sum);
        }
        
        System.out.println(answer);
    }
}