백준 1715번 - 카드 정렬하기

문제

백준 1715번 - 카드 정렬하기

아이디어

• 고르는 순서가 결과에 영향을 미치는 요인이 된다.
• 우선순위 큐를 사용한다.
• 가장 적은 카드 두 묶음을 꺼내서 합한 다음 다시 우선순위 큐에 삽입한다.
• 위 과정을 우선순위 큐에 카드 묶음이 하나 남을 때까지 반복한다.

예상 시간 복잡도

• 우선순위 큐 poll과 offer 시간 복잡도 : O(log n)
• 데이터 N개 만큼 수행한다고 하면 O(n log n)
• 예상 시간 복잡도 : 약 O(1,660,000)

코드 구현

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

public class BJ_1715 {
    public static void main(String[] args) throws IOException {
    
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        PriorityQueue<Integer> qu = new PriorityQueue<>();

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

        int result = 0;

        while (qu.size() > 1) {
            int card1 = qu.poll();
            int card2 = qu.poll();

            int sum = card1 + card2;
            result += sum;

            qu.offer(sum);
        }

        System.out.println(result);
    }
}