[백준_JAVA_알고리즘] 1715 카드 정렬하기 #힙 #우선순위 큐

 

카드를 PriorityQueue를 이용해서 (자동으로) 오름차순 정렬을 합니다. 

카드 묶음을 합치고 다시 누적하기 위해서 poll(), add() 합니다.

 

정렬은 Arrays.sort를 이용할 수도 있지만, 지속적으로 값을 꺼내고 저장하기 위해서는 PriorityQueue가 더 효율적입니다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        int N = Integer.parseInt(stringTokenizer.nextToken());

        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        int answer = 0;

        for(int i = 0; i < N; i++){
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            priorityQueue.add(Integer.parseInt(stringTokenizer.nextToken()));
        }

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

 

.

.

.

 

문제는 아래에서 확인할 수 있습니다.

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