[소프티어] 금고털이(JAVA)

문제

https://softeer.ai/practice/6288

---

풀이(13분)

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

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()); // 귀금속의 종류

        List<Jewel> list = new ArrayList<>(); // 보석 리스트

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int weight = Integer.parseInt(st.nextToken());
            int price = Integer.parseInt(st.nextToken());
            list.add(new Jewel(weight, price)); // 리스트에 보석 추가
        }

        // 가격 내림차순 정렬 (Comparable 구현)
        Collections.sort(list);

        int answer = 0;
        int idx = 0;

        while (w > 0 && idx < list.size()) {
            Jewel jewel = list.get(idx);
            int takeWeight = Math.min(jewel.weight, w); // 배낭에 넣을 수 있는 무게 결정
            answer += takeWeight * jewel.price;
            w -= takeWeight;
            idx++;
        }

        System.out.println(answer);
    }

    // Comparable을 구현한 Jewel 클래스
    static class Jewel implements Comparable<Jewel> {
        int weight;
        int price;

        public Jewel(int weight, int price) {
            this.weight = weight;
            this.price = price;
        }

        @Override
        public int compareTo(Jewel other) {
            return Integer.compare(other.price, this.price); // 가격 기준 내림차순 정렬
        }
    }
}

 

---

문제 풀이 전략

 

이전부터 보면, 소프티어는 참 정렬에 대한 부분을 좋아하는 것 같다.

 

이 문제 또한 마찬가지였다.

 

나의 경우에 대부분 Collections.sort(list, (o1, o2) ->{}) 방식을 즐겨 사용했으나 새로운 방법에도 익숙해지고 싶어 compareTo 메서드를 오버라이드 하였다.

 

compare 메서드 같은 경우 앞의 매개변수가 크면 양수를 반환해 주어 내림차순 정렬을 하는 것에 이용하였다.

 

이 외에는 기본적으로 보석마다 각자 고유한 무게 당 금액이 있는 것이 아닌 일정한 무게당 가격이 존재하였다.

-> 가격을 기준으로 내림차순 정렬하여, 가격이 제일 좋은 것부터 채워넣는 방식으로 진행했다.