[백준] 1715번. 카드 정렬하기 (JAVA)

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

---

문제

---

풀이

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        
        for(int i = 0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            queue.offer(Integer.parseInt(st.nextToken()));
        }

        int sum = 0;

        if(queue.size() == 1){
        }else{
            while(true){
                int temp = 0;
                int a = queue.poll();
                int b = queue.poll();

                sum += a + b;
                temp = a+ b;

                if(queue.isEmpty()){
                    break;
                }
                queue.offer(temp);

            }
        }

        System.out.println(sum);

    }

}

 

문제의 설정은 우선순위 큐만 떠올릴 수 있다면 쉽다고 생각된다. 작은 순서부터 더하기 시작하여 큰 순서까지 더해가면 된다. 이때, 작은 숫자를 더하면 커질 수 있으니 단순 배열의 정렬을 사용하여 더해나가는 것이 아니라 큐에 다시 넣은 뒤 순서를 맞춰 더한다는 것에 초점을 두면 된다.

문제의 풀이와 별개로 NullPointerException이 나와 고민을 했다. 그 이유는 처음에는

while(true){
int temp = 0;
int a = queue.poll();
int b = queue.poll();

sum += a + b;
temp = a+ b;

if(queue.isEmpty()){
break;
}
queue.offer(temp);

}

이 문장만 둔 채로 진행을 했다. 여기서 문제는 큐에서 poll 즉 요소를 두번 꺼내고 시작한다는 것이다. 다만 문제의 조건을 살펴보면 n의 크기가 1부터 시작하게 된다. 이 경우 큐에서 두 개의 요소를 꺼내려했기 때문에 문제가 발생하는 것이다.

 

또한, n의 크기에 맞춰 if-else문을 도입한 뒤에도 문제를 틀렸다. queue.size 가 1일 때 sum = queue.poll()을 했기 때문이다. n이 1일 때를 발견한 것 + n이 2 이상일 때의 풀이에 기준을 맞추어 단순하게 생각했기에 발생한 실수였다. 문제의 조건을 명확히 이해하면 n이 1일 때는 카드를 한 번도 바꿀 이유가 없다.(정렬되어 있기 때문이다)