[JAVA] 백준 1715 카드 정렬하기_최소힙

 

문제 : 

https://www.acmicpc.net/problem/1715

 

접근 : 

  - 카드 뭉치를 최소 힙에 넣는다.

 

  - 카드에서 최소 뭉치 2개를 꺼내 비교 횟수를 구한다( card1 + card2 )

 

  - 구한 비교 횟수를 다시 최소 힙에 넣고 다음 최소치 뭉치 2개를 꺼내 비교 횟수를 구한다.

 

  - 힙의 사이즈가 1이 될 때까지 반복 후 끝날 때, 까지 비교 횟수를 누적한 합산한 값을 출력한다.

 

 

 

 

코드 구현 : 

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

public class Main {

    private final PriorityQueue<Integer> cards;

    public Main(){
        cards = new PriorityQueue<>();
    }

    public void addUnit(int unit){
        cards.add(unit);
    }

    private int run(){
        if(cards.size() == 1) return 0;
        int temp;
        int ans = 0;
        while(cards.size() > 1){
            temp = cards.poll() + cards.poll();
            ans += temp;
            cards.add(temp);
        }
        return ans;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Main m = new Main();
        int t = Integer.parseInt(br.readLine());

        for(int i = 0 ; i < t ; i++){
            m.addUnit(Integer.parseInt(br.readLine()));
        }
        System.out.println(m.run());
    }
}