[백준] 파일 합치기3 : 13975 : Java - 그리디 (G4)

1.  💎 문제

13975번: 파일 합치기 3

• 모든 장을 합쳤을 때 최소 비용을 구한다
• 2개를 선택해서 더한다.

---

 

2. 🤔 어떻게 풀까

최소의 비용을 얻을 수 있는 방법은?

 예제를 통해 어떤 경우에 최소가 될 수 있는지 분석했다. 알아낸 점은 일찍 선택할 수록 더 많은 횟수를 더하게 된다는 점이었다. 이 문제는 합쳐진 것도 계속 더해가면서 누적을 해야되기 때문이다. 그래서 최대한 작은 수대로 먼저 2개씩 더해야겠다고 생각했다. 생각을 적용해서 다시 예제를 풀어보니 개별 파일 중에서 가장 작은 수 2개를 선택하는 것이 아닌, 합쳐진 임시 파일도 포함해서 가장 작은 사이즈 2개를 선택해야 한다는 것을 알았다.

 

이제, 임시 파일을 포함해서 가장 작은 파일 2개를 합치고, 합친 파일을 다시 삽입하는 연산을 최종적으로 1개의 파일이 남을 때까지 반복한는 과정을 코드를 통해 확인한다.

 

3. 💡 로직

파일 사이즈 입력 받기

 가장 작은 사이즈의 파일을 매번 뽑아야 하므로, 매번 정렬을 해서 뽑게 되면 시간 초과가 난다. 그러므로 삽입 시 정렬을 해주는 `TreeMap`을 이용하였다. 중복된 수를 저장할 수 없는 Set과 Map의 특징 상 사이즈를 key로, 중복된 횟수를 value로 함께 저장하여 이용한다. 

            TreeMap<Long, Long> nums = new TreeMap<>();
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int i =0; i<k; i++){
                long key = Integer.parseInt(st.nextToken());
                nums.put(key, nums.getOrDefault(key,0L) +1);
            }

 

가장 작은 2개의 파일을 선택하여 합친 후 다시 삽입

count를 함께 관리 해줘야 되어서 코드가 복잡하지만 결국은 2개를 `nums` 에서 빼내어 `result`에 2개의 사이즈를 더한 후, 합쳐친 파일의 크기를 삽입한다. 이를 파일 1개만 남을 때까지 반복하고 결과로 `result`를 출력한다.

	while(nums.size() != 1){
                // 매번 가장 작은 거 2개를 뽑고 합쳐서 하나로 집어넣기
                long n1 = nums.firstKey();
                if(nums.firstEntry().getValue() == 1){
                    nums.pollFirstEntry();
                } else{
                    nums.put(n1, nums.get(n1)-1);
                }

                long n2 = nums.firstKey();
                if(nums.firstEntry().getValue() == 1){
                    nums.pollFirstEntry();
                } else{
                    nums.put(n2, nums.get(n2)-1);
                }
                result += n1+n2;
                nums.put(n1+n2, nums.getOrDefault(n1+n2,0L) +1);

            }

 

 

4.  🖥️ 전체 코드 - TreeMap 

import java.awt.*;
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;


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));

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

        for(int t=0; t<T; t++){
            long result=0;
            int k = Integer.parseInt(br.readLine());
            TreeMap<Long, Long> nums = new TreeMap<>();
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int i =0; i<k; i++){
                long key = Integer.parseInt(st.nextToken());
                nums.put(key, nums.getOrDefault(key,0L) +1);
            }

            while(nums.size() != 1){
                // 매번 가장 작은 거 2개를 뽑고 합쳐서 하나로 집어넣기
                long n1 = nums.firstKey();
                if(nums.firstEntry().getValue() == 1){
                    nums.pollFirstEntry();
                } else{
                    nums.put(n1, nums.get(n1)-1);
                }

                long n2 = nums.firstKey();
                if(nums.firstEntry().getValue() == 1){
                    nums.pollFirstEntry();
                } else{
                    nums.put(n2, nums.get(n2)-1);
                }
                result += n1+n2;
                nums.put(n1+n2, nums.getOrDefault(n1+n2,0L) +1);

            }
            bw.write(result+"\n");
        }


        bw.flush();

        bw.close();
        br.close();

    }

}

 

 

5.  또 다른 방법, 우선 순위 큐 이용

나는 정렬을 따로 하지 않고 가장 작은 원소를 찾기 위해 TreeMap을 이용하였지만, 바로 TreeMap과 같은 역할을 하면서 더 간단하게 구현할 수 있는 자료구조가 있다. 바로 우선순위 큐(Priority que)이다. 중복 값도 포함하여 정렬을 하기 때문에 따로 중복 값을 관리할 필요도 없다. 

5.1  🖥️  전체코드 - 우선 순위 큐

우선 순위 큐를 이용한 풀이법을 아래와 같다. 코드가 훨씬 간단해진 것을 확인할 수 있다.

import java.awt.*;
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));

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

        for(int t=0; t<T; t++){
            long result=0;
            int k = Integer.parseInt(br.readLine());
            PriorityQueue<Long> que = new PriorityQueue<>();
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int i =0; i<k; i++){
                long key = Integer.parseInt(st.nextToken());
                que.add(key);
            }

            while(que.size() !=1){
                // 매번 가장 작은 거 2개를 뽑고 합쳐서 하나로 집어넣기
                long n1 = que.poll();
                long n2 = que.poll();
                result += n1+n2;
                que.add(n1+n2);
            }
            bw.write(result+"\n");
        }


        bw.flush();

        bw.close();
        br.close();

    }

}

 

성능 차이는 우선 순위큐가 약 4000kb만큼의 메모리 향상을 보였고, TreeMap이 300ms 더 빠르다.