[소프티어] 금고털이 레벨2 자바 풀이

https://softeer.ai/practice/6288

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

 

 

 

 

처음에는 재귀로 풀어야 하나 싶었다. 하지만 Item 클래스를 두고 ArrayList를 이용해서 정렬을 해주면 되었다.

원하는 대로 정렬을 하기 위해서는 Collections 이라는 것을 알게 되었다.

Collections.sort(items, (i1, i2) -> {  
    return i2.price - i1.price;  
});

Collections.sort()메서드는 정렬 시 두 요소의 순서를 결정하기 위해 Comparator의 비교 결과를 사용한다.
이때 반환값이 다음과 같은 의미를 가진다.

• 양수 (>0): i2가 i1보다 클 때 위치를 바꾼다. 따라서 i2가 앞으로 오고 i1이 뒤로 간다.
• 0: 두 값이 같아서 순서를 유지한다.
• 음수 (<0): i2가 i1보다 작을 때 그대로 유지한다. 즉, i1이 앞에 남는다.

그리고 i1.price - i2.price 로 하면, Collections.sort()는 i1과 i2의 오름차순으로 정렬 된다.

• 작은 값이 앞쪽에 오고 큰 값이 뒤쪽으로 이동하게 되어 오름차순 정렬이 된다.

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

class Item {
    int weight;
    int price;

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

public class Main {
    private static int w;
    private static int n;
    private static int dap;
    private static ArrayList<Item> items = new ArrayList<>();

    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 = new StringTokenizer(br.readLine());

        w = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());


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

        Collections.sort(items, (i1, i2) -> { // items price 내림차순 정렬
            return i2.price - i1.price;
        });

        for (Item item : items) {
            if (w == 0) break; // 가방이 꽉 찼으면 종료

            if (w >= item.weight) { // 가방에 물건이 다 들어가는 경우
                dap += (item.price * item.weight); // 가격을 더해준다.
                w -= item.weight;
            } else { // 가방에 물건이 다 들어가지 않는 경우
                dap += (item.price * w); // 남은 무게만큼만 가격을 더해준다.
                w = 0;
            }
        }

        bw.write(dap + "\n");

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

 

클리어