문제

카드 정렬하기 - 골드 4

---

문제 이해

• 매 순간 가장 작은 카드 두 묶음을 두 개씩 비교한다.
  -> 정렬 필요 --> Priority Queue 필요

예를 들어 90, 80, 60, 100의 카드 묶음이 있다고 한다면
60 + 80
+
90 + 100
+
(60 + 80) + (90 + 100)
= 660 이 된다.

---

코드

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

public class CardSort_1715 {
  static int N;
  static PriorityQueue<Long> cardSet;
  static Long count = 0l;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken());
    cardSet = new PriorityQueue<>();

    for (int i = 0; i < N; i++) {
      st = new StringTokenizer(br.readLine());
      cardSet.add(Long.parseLong(st.nextToken()));
    }

    while (cardSet.size() > 1) {
      long front = cardSet.poll();
      long back = cardSet.poll();

      count += front + back;
      cardSet.add(front + back);
    }

    System.out.println(count);
  }
}

---

코드 설명

1. 입력과 동시에 Priority Queue에 넣는다. 이때 오름차순으로 Queue에 저장된다.
2. PQ의 사이즈가 1보다 크다면 계속해서 반복한다.
3. 앞에 두개를 뺀다.(즉, 가장 작은 값 두개를 뺀다) 그리고 이를 더해서 다시 PQ에 넣어준다.
4. 두 개의 합을 count에 더해준다.

---