[골드 4] 카드 정렬하기

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

1715번: 카드 정렬하기

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 1 <= N <= 100,000
        // 1 < = size_card <= 1,000

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

//        ArrayList<Integer> size_cards = new ArrayList<>();
        PriorityQueue<Integer> size_cards = new PriorityQueue<>();

        for (int i = 0; i < N; i++) {
            size_cards.add(Integer.parseInt(br.readLine()));
        }

        int answer = 0;

        while (size_cards.size() != 1) {
            int a = size_cards.remove();
            int b = size_cards.remove();
            answer += a + b;
            size_cards.add(a + b);
        }

        bw.write(answer + "\n");
        bw.flush();
        bw.close();
    }
}

합이 최소가 되어야 하므로 결국 합을 하는 각각이 최소가 되어야 한다

 

실패)

자료구조를 ArrayList로 설정하여 index 0 1 제거 후 값 추가 후 정렬

while 문장이 O(N * NlogN) 이 걸렸다

 

성공)

자료구조를 우선순위 큐로 변경하고 삭제와 삽입이 logN이므로

O(NlogN)으로 해결

 

왜 쓸 수 있냐?

항상 최솟값 2개를 구해서 덧셈 후 자료구조에 넣어줘야 하는 시스템이다