[Softeer] 금고털이 (★★☆☆☆)

문제

: 가방에 W만큼 챙겨서 가치가 최대가 되게하기

W: 채울 수 있는 최대 무게 (kg)

N: 귀금속의 종류

P: 귀금속 가격 (N번째 귀금속은 kg당 P가격) 

 

1 ≤ N ≤ 106인 정수

1 ≤ W ≤ 104인 정수

1 ≤ Mi, Pi ≤ 104인 정수

문제 링크 : https://softeer.ai/practice/info.do?idx=1&eid=395&sw_prbl_sbms_sn=141855

---

원리

탐욕 알고리즘

우선순위큐

---

풀이방법

가령, 100kg 가방이 있다면, 

가치가 kg당 2인 금속 70kg 중 70kg을,

가치가 kg당 1인 금속 90kg 중 30kg를 담으면 베스트다.

따라서, 70*2 + 30*1 = 170이 최대밸류가 될 수 있다.

---

나의 코드

1. HashMap, ArrayList, Deque, Stream을 사용한 방법 : Softeer의 자바 11에선 Stream을 지원하지 않는다(?)

 

2. int[], Deque를 사용한 방법 : 일부 시간초과 발생

public class SafeCreacker {

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

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int bag = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        int [] arr = new int [1000000];
        Deque<Integer> dq = new ArrayDeque<>();
        for(int i=0; i<N ; i++) {
            StringTokenizer stN = new StringTokenizer(br.readLine(), " ");
            int M = Integer.parseInt(stN.nextToken());
            int P = Integer.parseInt(stN.nextToken());
            arr[P] += M;
            dq.addFirst(P);
        }
        int result = 0;
        while(bag>0) {
            int temp = dq.pollFirst();
            if(bag>arr[temp]) {
                result += (temp*arr[temp]);
                bag-=arr[temp];
            }
            else {
                result += (temp *bag);
                bag = 0;
            }
        }
        System.out.println(result);
    }
}

 

3. HashMap + Deque사용 : 일부 시간초과 발생

public class SafeCreacker {

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

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int bag = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        Deque<Integer> dq = new ArrayDeque<>();
        Map<Integer,Integer> map = new HashMap<>();
        for(int i=0; i<N ; i++) {
            StringTokenizer stN = new StringTokenizer(br.readLine(), " ");
            int M = Integer.parseInt(stN.nextToken());
            int P = Integer.parseInt(stN.nextToken());
            if(map.containsKey(P)) map.put(P, map.get(P)+M);
            else map.put(P,M);
            dq.addFirst(P);
        }

        int result = 0;
        while(bag>0) {
            int temp = dq.pollFirst();
            if(bag>map.get(temp)) {
                result += (temp*map.get(temp));
                bag-=map.get(temp);
            }
            else {
                result += (temp *bag);
                bag = 0;
            }
        }
        System.out.println(result);
    }
}

 

4. Map + ArrayList 사용 [ 일부 시간 초과 ]

: 키-밸류로 가치-용량을 저장할 map, 각 키값을 저장해둘 ArrayList

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
    StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    int W = Integer.parseInt(st.nextToken());
    int ea = Integer.parseInt(st.nextToken());
    Map<Integer, Integer> map = new HashMap<>();
    int result = 0;
    List<Integer> values = new ArrayList<>();
    for(int  i = 0; i<ea ; i++) {
        StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
        int kg = Integer.parseInt(st2.nextToken());
        int val = Integer.parseInt(st2.nextToken());
        map.put(val, kg);
        values.add(val);
    }
    values.stream().sorted();

    for(int i = values.size()-1 ; i>=0 ; i--) {
        int temp = map.get(values.get(i));
        if(temp<=W) {
            W -= temp;
            result += (values.get(i) * temp);
        }
        else {
            result += (W* values.get(i));
            break;
        }
    }
    System.out.println(result);
}

 

5. PriorityQueue + 객체 사용 [ 정답 ]

: 주어진 문제는 최소한의 속도로 풀어야 하는게 포인트

: 따라서 출제 의도는 PriorityQueue를 사용해야하는 문제

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

public class safecracker {

    public static void main(String[] args) throws IOException {
        // 입력을 받기 위한 버퍼 (최소한의 입력 속도)
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 가방무게와 금속의 갯수를 받기위한 부분
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int W = Integer.parseInt(st.nextToken());
        int ea = Integer.parseInt(st.nextToken());

        // 결과값이 될 부분
        int result = 0;

        /**
         * 핵심 부분
         * 1. 우선순위큐를 이용해 가치가 큰 순(숫자로 치면 역순)으로 정렬을 해줘야 한다.
         *    이때, 우선순위큐가 아닌 다른 자료구조의 sort를 사용하는 순간 시간 초과다.
         * 2. 우선순위큐에 값을 객체로 받아서 넣어준다. (kg: 무게, val: 가치, metal: 귀금속)
         */
        PriorityQueue<metal> pq = new PriorityQueue<>((a,b) -> b.val - a.val);
        for(int  i = 0; i<ea ; i++) {
            StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
            metal metal = new metal(Integer.parseInt(st2.nextToken()), Integer.parseInt(st2.nextToken()));
            pq.add(metal);
        }

        /**
         * 이제 가방의 용량이 0이 될 때까지 반복만 해주면 된다.
         * 1. 가방용량이 더 크면, 지금 뽑은 물질의 가치 * 최대가용량을 넣어주고, 그 만큼 가방의 용량에서 빼준다.
         * 2. 가방용량이 더 부족하면, 지금 뽑은 물질의 가치 * 가방의 남은 용량만큼 넣어주고, 가방의 남은 용량은 0으로 해준다.
         */
        while(W!=0) {
            metal now = pq.poll();
            if(W>=now.kg) {
                W -= now.kg;
                result += (now.kg * now.val);
            } else {
                result += (W * now.val);
                W = 0;
            }
        }
        System.out.println(result);
    }

    /**
     * 물질을 객체로 만들기 위한 이너클래스
     */
    private static class metal {
        private int kg;
        private int val;
        public metal(int kg, int val) {
            this.kg = kg;
            this.val = val;
        }
    }
}

 

---

레퍼런스 코드

참고 링크 : https://velog.io/@frobenius/Softeer-%EA%B8%88%EA%B3%A0%ED%84%B8%EC%9D%B4-java