[백준 1202] - 보석도둑(JAVA)[골드2]

문제

https://www.acmicpc.net/problem/1202

1202번: 보석 도둑

 

문제 풀이

시간초과에 많이 좌절했던 문제였다.

배낭문제랑 비슷해서 접근방법은 배낭문제랑 비슷하게 했다.

 

특이한 점은 가방마다 보석을 하나 담아야 하기 때문에 그 부분을 신경 써줬다.

 

우선 입력받은 보석을 정렬했다.

• 우선 무게 순으로 내림차순 정렬했다.
• 무게가 같다면 보석의 가치로 내림차순 정렬했다.

이유는 단위무게가 높더라도, 가벼운 보석을 용량이 큰 가방에 넣으면 안 되기 때문이다.

단위무게로 보석을 정렬하면 100만큼 담을 수 있는 가방에 가벼운 무게의 보석이 들어가기 때문에

우리는 무거운 보석 중에 가장 가치 있는 보석을 많이 담을 수 있는 가방에 담아야 한다.

 

이다음은 보석을 가방에 담으면 되는데, 여기서 많은 문제가 발생했다.

 

초기 코드

   public static void insertJewelry(){
        for(int i=k-1; i>=0; i--){ 
            for(int j=0; j<n; j++){
                if(visit[j])
                    continue;
                if(bags[i]<jewelrys[j].w){
                    continue;
                }
                bags[i]=0;
                answer+=jewelrys[j].v;
                visit[j]=true;
                break;
            }
        }
    }

시간복잡도는 n*k이다.

k개의 가방에 n개의 보석을 담는 과정이다.

list로 보석을 선언하지 않았기 때문에 보석을 담았다는 표시를 visit로 해줬다.

그다음 보석의 무게가 가방을 초과한다면 continue를 통해서 걸러주고,

if문을 통과하면 보석을 담고 탐색을 중단했다.

... 는 시간초과였다.

n과 k의 입력값이 너무 커서 n*k 사실상 n^2 알고리즘으로 통과할 수가 없었다.

아마 보석을 담고, 보석을 거르는 방법을 visit로 했기 때문에 탐색의 수가 너무 많기 때문이었다.

 

 

구글링을 하고 여러 코드를 보고 든 생각은

보석을 검사하고, 걸러진 보석은 빼주자였다.

나는 visit로 보석을 뺏고, 구글링 코드에서는 우선순위 큐를 사용해서 무게에 담을 수 있는 보석을 최대한 걸러주고,

가장 적합한 보석을 담아줬다.

 

변경된 코드

public static void insertJewelry() {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int i = k - 1; i >= 0; i--) { //가방순으로 돌림. 가방은 무게순으로 내림차순.

            while (!jewelries.isEmpty() && bags[i] >= jewelries.peek().w) {
                queue.add(jewelries.poll().v*-1);
            }

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

현재 가방에 담을 수 있는 보석을 후보로 추리고, 가장 무거운 녀석을 더해줬다.

이러니 시간초과가 해결되었다.

 

시간복잡도를 신경 써줘야 하는데, 그런 부분에서 너무 부족한 거 같아서 체계적으로 공부를 해야 하나 싶다..

 

전체 코드

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

public class Main {

    static BufferedReader br;
    static StringTokenizer st;
    static int n, k;
    static long answer = 0;

    static Integer[] bags;
    static PriorityQueue<Jewelry> jewelries = new PriorityQueue<Jewelry>();

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        input();
        sortBags();
        insertJewelry();
        System.out.print(answer);
    }

    public static void input() throws IOException {
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken()); //보석 개수
        k = Integer.parseInt(st.nextToken()); //가방 개수
        bags = new Integer[k];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            jewelries.add(new Jewelry(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()))); // 무게 정보)
        }
        for (int i = 0; i < k; i++) {
            st = new StringTokenizer(br.readLine());
            bags[i] = Integer.parseInt(st.nextToken());
        }
    }

    public static void sortBags() {
        Arrays.sort(bags, (o1, o2) -> o2 - o1);
    }

    public static void insertJewelry() {
        PriorityQueue<Jewelry> queue = new PriorityQueue<>(new Comparator<Jewelry>() {
            @Override
            public int compare(Jewelry o1, Jewelry o2) {
                return o2.v - o1.v;
            }
        });
        for (int i = k - 1; i >= 0; i--) { //가방순으로 돌림. 가방은 무게순으로 내림차순.

            while (!jewelries.isEmpty() && bags[i] >= jewelries.peek().w) {
                queue.add(jewelries.poll());
            }

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

    static class Jewelry implements Comparable<Jewelry> {
        int v;
        int w;

        public Jewelry(int w, int v) {
            this.w = w;
            this.v = v;
        }

        @Override
        public int compareTo(Jewelry o) {
            if (this.w == o.w) return o.v - this.v;
            return this.w - o.w;
        }
    }
}