[백준] 1715 - 카드 정렬하기

난이도 - G4

사용 개념 - 구현, 자료구조(PriorityQueue)

풀이 시간 -  20분 ( 설계 10분, 구현 10분 )

핵심 키워드 

 * 1. 문제의 설명에 의하면 결국 가장 작은 값 2개를 꺼낸 후 덧셈을 진행하고, 다시 Prioirty Queue에 넣어야 한다.

        -> 배열로 진행하면 인덱스 처리가 복잡해진다. Priority Queue를 사용해서 풀라고 만든 문제같다.

 * 2. int의 범위로는 할 수 없다. long을 사용하여야 한다. ( 최악의 상황 )

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main {
    static StringTokenizer st;
    static StringBuilder sb;
    static int n,m,k;
    public static void main(String[] args)throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        n = Integer.parseInt(br.readLine());
        for(int i=0; i<n; i++){
            pq.offer(Integer.parseInt(br.readLine()));
        }
        long result=0;
        while(pq.size()>1){
            int sum = pq.poll() + pq.poll();
            result += sum;
            pq.offer(sum);
        }
        System.out.println(result);
    }
}

 

- 골드4 난이도 문제치고는 코드가 매우 간결하고 Prioirty Queue를 사용한 것이 끝이다.

- 보통 Queue를 통해 반복을 돌릴 때 while(pq.isEmpty())를 주로 하는데, 이 문제는 1개의 숫자만 남을 때 까지 진행해야 하기 때문에 while(pq.size() > 1)로 반복을 진행했다.