[자바/그리디] 코드트리. 쪼개어 배낭 채우기

문제

문제 링크

해석

이 문제는 fractional knapsack 유형을 학습하기 위한 연습문제여서 로직 구성을 고민하진 않았다.

 

딱 한 가지 레슨런이 있다면, 단위 가치 순으로 정렬을 하기 위해 나는 최초 로직에서 트리맵을 사용하려고 했다. <단위 가치, 무게>를 트리맵에 넣어서 정렬을 내가 별도로 처리하지 않고 자료구조로 퉁치려고 했는데, key는 중복을 허용하지 않는단 사실을 뒤늦게 알고 아차 했었다... 실전에서는 이런 사소한 디버깅을 하기 어려울 거고, 시간도 부족하니 그냥 정렬 하기 귀찮다고 트리 구조를 이용하는 로직 구성은 하지 않기로 결심했다...(나름의 레슨런)

 

만약 자료구조를 이용해서 정렬 로직을 대신하고 싶다면 웬만해선 데이터 그룹을 클래스로 묶어서 우선순위큐를 활용하는 게 이롭다. 단, 주의할 점은, 배열을 이용하면 그냥 단순 iteration을 하면 되지만, 우선순위 큐는 완전이진트리 기반의 힙 구조라서 배열처럼 iteration을 하면 우리가 이해하는 숫자 순서대로 나오지 않는다. 따라서 poll연산을 반복하면서 수행해줘야 한다. (만약 왜 단순 iteration을 하면 안되는지 모르는 분은 자바에서 배열을 가지고 트리를 구현할 때 자식 노드의 값을 어디 인덱스에 저장하는지 이해하는 과정이 필요하고, 이는 제가 세그먼트 트리 학습할 때 간단히 다뤘으니 참고하셔도 좋을 것 같습니다.)

 

포인트가 자료구조가 아닌 문제였는데, 본의아니게 자료구조에 대하여 다시 돌아보게 된 문제였다...

코드

배열 풀이

import java.io.*;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class Main {
    /*
    * 실행 시간 : 645 ms
    *
    * 사용 메모리 : 26 MB
    *
    * 시간복잡도 : O(N * logN) // 정렬에 log N 소요
    * */
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        Jewel[] arr = new Jewel[n];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            double w = Integer.parseInt(st.nextToken());
            double v = Integer.parseInt(st.nextToken());
            arr[i] = new Jewel(w, v);
        }
        Arrays.sort(arr, Comparator.comparingDouble(o -> -o.value/o.weight)); // 단위 가치 내림차순

        double ans = 0;
        double bag = 0;

        for (Jewel jewel : arr) {
            double weight = jewel.weight;
            double value = jewel.value;
            if (bag + weight <= m) {
                ans += value;
                bag += weight;
            } else {
                double fractionValue = (value * (m - bag)) / weight;
                ans += fractionValue;
                break;
            }
        }
        bw.write(String.format("%.3f", ans));

        br.close();
        bw.flush();
        bw.close();
    }

    private static class Jewel {
        double weight;
        double value;

        private Jewel(double w, double v) {
            weight = w;
            value = v;
        }
    }
}

최소힙 풀이

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

public class Main {
    /*
    * 실행 시간 : 685 ms (오히려 더 걸림)
    *
    * 메모리 : 26 MB
    *
    * 시간복잡도 : O(N * logN) // 우선순위큐 삽입삭제에 log N 소요
    * */
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        PriorityQueue<Jewel> pq = new PriorityQueue<>(Comparator.comparingDouble(o -> -o.value / o.weight));

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            double w = Integer.parseInt(st.nextToken());
            double v = Integer.parseInt(st.nextToken());
            pq.add(new Jewel(w, v));
        }

        double ans = 0;
        double bag = 0;

        while (!pq.isEmpty()) { // 배열과 다르다는 걸 주의
            Jewel jewel = pq.poll();
            double weight = jewel.weight;
            double value = jewel.value;
            if (bag + weight <= m) {
                ans += value;
                bag += weight;
            } else {
                double fractionValue = (value * (m - bag)) / weight;
                ans += fractionValue;
                break;
            }
        }
        bw.write(String.format("%.3f", ans));

        br.close();
        bw.flush();
        bw.close();
    }

    private static class Jewel {
        double weight;
        double value;

        private Jewel(double w, double v) {
            weight = w;
            value = v;
        }
    }
}