[소프티어] 금고털이 - JAVA

 

 

Lv.2의 문제이다.

 

https://softeer.ai/practice/6288

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

---

 

 

# 문제 설명

루팡은 배낭을 하나 메고 은행금고에 들어왔다. 금고 안에는 값비싼 금, 은, 백금 등의 귀금속 덩어리가 잔뜩 들어있다. 배낭은 W ㎏까지 담을 수 있다.

 

각 금속의 무게와 무게당 가격이 주어졌을 때 배낭을 채울 수 있는 가장 값비싼 가격은 얼마인가?

 

루팡은 전동톱을 가지고 있으며 귀금속은 톱으로 자르면 잘려진 부분의 무게만큼 가치를 가진다.

 

# 제약조건

1 ≤ N ≤ 10^6인 정수

1 ≤ W ≤ 10^4인 정수

1 ≤ Mi, Pi ≤ 10^4인 정수

# 입력형식

첫 번째 줄에 배낭의 무게 W와 귀금속의 종류 N이 주어진다. i + 1 (1 ≤ i ≤ N)번째 줄에는 i번째 금속의 무게 Mi와 무게당 가격 Pi가 주어진다.

 

# 출력형식

첫 번째 줄에 배낭에 담을 수 있는 가장 비싼 가격을 출력하라.

 

 

문제 해결 전략

 

무게당 가격이 큰 순서대로 무게를 곱해서 결과를 구해야 할 것이다. 그렇다면 정렬이 필요할 것이다.

이때 Map을 사용해서 같은 무게당 가격을 갖고 있다면 하나로 보고 그렇게 하면 정렬 시 이점을 가질 수 있을 것이라는 생각을 가졌다.

 

 

---

 

# 1

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

public class Main {


    public static void main(String[] args)throws IOException {

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        int w, n;

        String a = bf.readLine();
        String[] b = a.split(" ");
        w = Integer.parseInt(b[0]);
        n = Integer.parseInt(b[1]);
        
        
        Map<Integer,Integer> mp = new HashMap<>();

        List<Integer> list = new ArrayList<>();

        for(int i=0;i<n;i++){
            String line = bf.readLine();
            String[] t = line.split(" ");

            if(mp.containsKey(Integer.parseInt(t[1]))){
                mp.put(Integer.parseInt(t[1]), mp.get(Integer.parseInt(t[1]))+Integer.parseInt(t[0]));
            }else{
                mp.put(Integer.parseInt(t[1]), Integer.parseInt(t[0]));
                list.add(Integer.parseInt(t[1]));
            }
            
        }

        list.sort(Collections.reverseOrder());

        int answer = 0;
        
        for(int i=0;i<list.size();i++){

            int p = list.get(i);

            int m = mp.get(p);

            if(w-m > 0){
                answer += m * p;
                w -= m;
            }else{
                answer += w * p;
                break;
            }
        }

        System.out.println(answer);


    }

}

 

 

 

Map을 사용하여 중복을 제거하는 이점을 가져가면서 깔끔하게 key 값을 정렬하고 싶었다.

이후 더 효율적인 코드를 찾기 위해 방식을 찾아보았다.

이때 찾은 것이 리스트 선언 시 맵의 keySet을 넘겨주는 것이었다.

 

# 2 : 개선된 버전

 

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

public class Main {


    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 n = Integer.parseInt(st.nextToken()); 
        
        
        Map<Integer,Integer> mp = new HashMap<>();


        for(int i=0;i<n;i++){
            st = new StringTokenizer(br.readLine());
            int m = Integer.parseInt(st.nextToken()); 
            int p = Integer.parseInt(st.nextToken()); 

            
            mp.put(p, mp.getOrDefault(p, 0) + m);
            
        }

        List<Integer> list = new ArrayList<>(mp.keySet());
        list.sort(Collections.reverseOrder());

        int answer = 0;
        
        for (int price : list) {
            
            int weight = mp.get(price);

            if (w - weight > 0) { 
                answer += weight * price;
                w -= weight;
            } else { 
                answer += w * price;
                break;
            }
        }

        System.out.println(answer);


    }

}

 

실제로 많이 개선 된 모습이다.

 

개선 된 점

1. 처음부터 Map과 list에 모두 데이터를 넣는 게 아닌 Map에만 getOrDefault를 사용하여 데이터를 깔끔하게 삽입하고 keySet을 리스트로 만들어 정렬한다.

2. StringTokenizer를 사용해 입력을 처리하여 메모리 소비를 줄인다.