[Java] 백준 13975 파일 합치기 3 - 골드4

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

13975번: 파일 합치기 3

 

 

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


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

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

    for (int tc =0; tc<testCnt; tc++) {
      int chapterCnt = Integer.parseInt(br.readLine().strip());

      StringTokenizer st = new StringTokenizer(br.readLine());
      PriorityQueue<Long> chapter = new PriorityQueue<>();

      for (int i=0; i<chapterCnt; i++)
        chapter.add(Long.parseLong(st.nextToken()));

      long result = 0;

      while(chapter.size() != 1) {
        long a = chapter.poll();
        long b = chapter.poll();

        result += a+b;
        chapter.add(a+b);
      }

      System.out.println(result);
    }
  }
}

• minHeap에 입력값을 모두 답는다
• heap의 size가 1이 될 때까지 반복한다
  • heap에서 최솟값 2개를 빼서 result에 더해주고
  • 최솟값 2개를 더해 다시 heap에 넣어준