[백준] 보석 도둑 1202번 - Java

[백준] 보석 도둑 1202번

풀이 참조

느리더라도 꾸준하게

나의 풀이

class Jewel {
    int mass;
    int value;

    Jewel(int mass, int value) {
        this.mass = mass;
        this.value = value;
    }
}

public class JewelThief {
    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());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        Jewel[] jewels = new Jewel[N];

        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int mass = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());
            jewels[i] = new Jewel(mass, value);
        }

        Arrays.sort(jewels, new Comparator<Jewel>() {
            @Override
            public int compare(Jewel o1, Jewel o2) {
                if(o1.mass == o2.mass) {
                    return (o2.value - o1.value);
                }

                return o1.mass - o2.mass;
            }
        });

        int[] bags = new int[K];
        for(int i = 0; i < K; i++) {
            bags[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(bags);

        PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.reverseOrder());
        long result = 0;
        for(int i = 0, idx = 0; i < K; i++) {
            while(idx < N && jewels[idx].mass <= bags[i]) {
                queue.offer(jewels[idx++].value);
            }

            if(!queue.isEmpty()) {
                result += queue.poll();
            }
        }

        bw.write(result + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

• 우선 혼자 해결하지 못하고 블로그를 참조하여 코드를 작성하였다.
• 일반적인 접근 방법으로 계산하면 시간 초과로 풀 수 없다. 우선 큐를 통해서 접근해야한다.
• 우선 입력받은 보석의 무게를 기준으로 오름차순, 만약 보석의 무게가 같다면 보석의 가격을 기준으로 내림차순을 해줘야 한다. 정렬을 하기 쉽도록 Jewel객체를 만들어서 new Comparator로 정렬을 해주었다.
• 그리고 가방의 무게를 입력받고 가방의 무게도 오름차순으로 정렬을 한다.
• 이제 우선 큐를 생성해준다. 단, 우선 큐의 기본 값은 오름차순 즉, 값이 작은 것 먼저 리턴을 해준다. 떄문에 Comparator.reverseOrder()를 사용해서 값이 큰 것부터 반환하도록 설정을 해준다.
• 이제 정렬된 인덱스가 N보다 작고, 보석의 무게가 배낭의 무게보다 작거나 같은동안 배낭에 큐에 보석의 가격들을 넣어준다.
• 이렇게 while문 반복이 끝난 후, 큐기 비어있지 않다면, 값을 꺼내와 answer에 더해준다. 이 때 큐는 Comparator.reverseOrder 상태이기 때문에 큐가 가지고 있는 가장 큰 값을 반환해준다.

느낀점

for(int i = 0, idx = 0; i < K; i++) {
            while(idx < N && jewels[idx].mass <= bags[i]) {
                queue.offer(jewels[idx++].value);
            }

우선 이 부분에서 메모리 초과가 나왔었다. 처음에는 idx를 밖으로 빼서 int idx = 0; 으로 정의를 했더니 그게 문제였다. 때문에 idx를 저렇게 for문 안에 정의하고 나서는 메모리 초과 없이 통과되었다.

        PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.reverseOrder());

우선 큐를 이런 식으로 우선순위를 설정할 수 있다는 것을 알았다. 앞으로 써먹을 일이 많을 듯 하다.