백준 1202번 - 보석 도둑

문제링크

 

 

 

문제 풀이 과정

보석을 가방에 넣는 로직에서 보석이 중복으로 들어가지 않는 것에 대해 오래 고민을 한 문제이다.

 

우선 보석의 무게와 비용을 한번에 담기 위해서 Item 클래스를 만들었다.

 

static class Item implements Comparable<Item>{
    int idx;
    int weight;
    int cost;

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

    @Override
    public int compareTo(Item o) {
        if(this.weight == o.weight){
            return o.cost - this.cost;
        }
        return this.weight - o.weight;
    }
}

 

보석은 무게가 가벼운 순으로 정렬되게 하였고, 만약 무게가 같을 때는 가치가 큰 순으로 정렬되게 클래스를 구성하였다.

또한 가방의 정보는 가벼운 순으로 정렬 하였다.

 

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

 

보석을 담는 것은 우선순위큐를 사용하였다.

이때 우선순위큐는 내림차순으로 설정해주었다.

여기서 내림차순으로 한 이유는 가장 가치가 큰 보석을 뽑아내기 위함이다.

 

for (int i = 0, j = 0; i < K; i++) {
    while (j < N && item[j].weight <= bag[i]) {
        pq.offer(item[j++].cost);
    }

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

 

보석이 가방 무게보다 같거나 작을 때까지 큐에 넣어 주는 것이 while 문이다.

가방에 넣을 수 있는 무게를 다 넣은 다음 while 문을 빠져 나와 큐가 비어있지 않으면 result 에 더해 준다.

이때 큐는 FIFO (First In First Out) 구조로 되어 있어 poll 로 나오는 데이터는 가방에 넣을 수 있는 가장 가치가 큰 보석이 해당 된다.

보석이 큐에 중복으로 들어가지 않도록 별도의 변수인 j 를 사용하였다.

 

현재 보석과 가방의 정렬 상태이다.

 

가방의 무게가 2일 때의 우선 순위큐에는 위 사진처럼 들어가게 된다.

그다음 보석의 무게가 현재 가방의 무게보다 크므로 while 문은 종료 되어 나오게 된다.

 

 

poll 을 하게 되면 맨 앞에 있는 값이 result 에 더해진다.

 

그 다음 가방의 무게는 10이고, 10보다 작을때까지 큐에 넣어 준다.

 

여기서 왜 큐를 비우지 않고 재 사용하는 것이며, 인덱스는 왜 또 별도로 관리를 하는 것이지? 라는 의문이 들었었다.

보석의 무게와 가방이 담을 수 있는 무게는 모두 오름차순으로 되어 있어서 직전 가방까지 담았던 보석을 그 다음 가방에도 넣을 수 있기 때문이다.

 

그러면 가방에는 보석이 중복되어 들어가지 않고 가장 가치가 큰 보석만 들어가게 된다.

 

전체코드