[백준] Gold 4 카드 정렬하기

https://www.acmicpc.net/problem/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()); // 10만 , 제한시간 2초

        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int i = 0; i < n; i++) {
            int size = Integer.parseInt(br.readLine());
            pq.add(size);
        }

        int answer = 0;
        // 1. 우선순위 큐에서 가장 우선 순위가 낮은 두 값을 찾아서 더하고 큐에서 빼준다.
        // 2. 두 값의 합을 answer에 더해주고, 우선순위 큐에 합을 넣는다.
        // 3. 1을 다시 진행한다.
        while(!pq.isEmpty()) {
            if (pq.size() < 2) break;
            int num1 = pq.poll();
            int num2 = pq.poll();
            int sum = num1 + num2;
            pq.add(sum);
            answer += sum;
        }
        System.out.println(answer);
    }
}

 

회고

골드 4라고 해서 긴장했는데 생각보다 어렵지 않았다.

 

문제에서 주어진 n값의 범위는 10만이고, 제한시간은 2초로 Nlog(N)까지 허용 가능하다.

 

우선순위 큐에 원소를 넣는 과정: O(N)

두 개 원소를 꺼내고, 다시 삽입하는 과정: O(logN), 하지만 이 과정을 N/2번 반복하므로 O(NlogN)이 된다.

 

즉, 내 코드 시간복잡도 상으로 2초안에 해결이 가능하다. 

 

문제 로직은 코드상에 써넣었다.