[BOJ - JAVA] 1715 - 카드 정렬하기 (우선 순위 큐)

# 주소

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

1715번: 카드 정렬하기

# 문제

# 문제 해설 및 코드 리뷰

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        PriorityQueue<Long> queue = new PriorityQueue<>();
        long sum = 0;
        for(int i = 0; i < n; i++){
            long x = Integer.parseInt(br.readLine());
            queue.offer(x);
        }
        while(queue.size() > 1){
            long a = queue.poll();
            long b = queue.poll();
            sum += a + b;
            queue.offer(a + b);
        }
        System.out.println(sum);
    }
}

int타입으로 작성하면 오류가 납니다.

이유는 n값이 10만까지 들어올 수 있기 때문에 10만번 수행해서 더해지는 총합의 값은 int의 max값인 21억값을 상회할 수 있기 때문입니다.

따라서 PriorityQueue와 queue원소와 총합의 값인 sum은 Long타입으로 선언해야 합니다.

        for(int i = 0; i < n; i++){
            long x = Integer.parseInt(br.readLine());
            queue.offer(x);
        }

일단 여기에서 x를 입력받고 queue에 모두 삽입합니다.

while(queue.size() > 1){
            long a = queue.poll();
            long b = queue.poll();
            sum += a + b;
            queue.offer(a + b);
        }

그런뒤 while문을 통해 queue의 size가 1보다 클 때 while문을 동작시키는데요.

이유는 queue.poll()을 두 번 시행할 것인데, queue의 크기가 2보다 크거나 같아야만 2번 poll수행했을 때 size()가 음수가 안나오기 때문입니다. 간단하죠?

따라서 long타입으로 선언한 a와 b를 queue에서 빼오고 모두 sum에 일단 더합니다.

그리고 더한 sum값을 queue에 다시 삽입합니다.

이렇게 함으로써 queue는 새로운 더해진 원소값을 가질테고 while문을 통해 반복수행하면서 다시 queue의 최초값이 제일 앞단에 튀어나오게 되며 poll()을 두 번 수행하여 또 더하고 이런식으로 반복되는 것입니다.

결과적으로 while문이 한 번 수행될 때마다 데이터의 총 size()는 1씩 감소하는 형태를 나타내겠네요.

그리고 한 번 while문이 수행될 때 시간 복잡도는 N번일어나는 것이 3번 일어나므로 O(N^2)만큼의 시간 복잡도를 나타냅니다.

참고하시면 좋겠습니다.