[알고리즘]백준1715 카드 정렬하기 -java

문제

생각

모든 카드묶음을 다합칠때 가장 적은 비교횟수이기때문에

앞서 합친 카드묶음을 계속 합하여 구하기때문에

가장 작은 카드묶음끼리 먼저 합쳐야 된다.

그래서 생각한 것이
1. 가장 작은 카드묶음순으로 정렬
2. 가장작은카드,2번째로작은카드 합치기
3. 다시 작은 카드묶음순으로 정렬

1~3번을 카드묶음리스트size가 1이 될때까지 반복

but 카드묶음의 갯수가 최대 100,000이다
100,000을 최대 100,000번 정렬하기때문에
퀵정렬로 구현한다해도
100,000*100,000= 10,000,000,000으로
시간초과 난다(백준기준 1초당 대략 1억이다.)

그래서 리스트가 아닌 우선순위 큐를 이용해서 3번과정을 건너뛰었다.

코드

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

public class baekjoon1715 {
    public static void main(String[]args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        PriorityQueue<Integer> pack = new PriorityQueue<>();
        for(int i=0;i<count;i++){
            pack.add(Integer.parseInt(br.readLine()));
        }

        int max=0;
        while(pack.size()>1){
            int a= pack.poll();
            int b = pack.poll();
            max+=a+b;
            pack.add(a+b);
        }
        System.out.println(max);
    }

}