[백준 node.js] 1202번_보석 도둑

백준 그리디 알고리즘 1202번_보석 도둑

난이도 : 골드IV 

해결못한 문제 : 시간 초과 or 메모리 초과

 

문제 설명

입출력

예제 입력2

4 4

1 100

2 200

13 300

10 500

10

10

10

14

=> 답 : 1100

 

문제 풀이 : 최대한 비싼 보석을 챙기는 것이 문제 핵심이다. 그러기 위해서는 제일 비싼 보석을 순차적으로 보석의 무게와 비슷한 가방을 찾아 넣어줘야한다. 만약 1kg짜리 보석을 10kg짜리 가방에 넣으면 비효율적이기 때문에 최대한 비슷한 가방을 찾아서 넣어야한다. 정리하면 다음과 같다.

1. 보석 가격을 기준으로 정렬을 해준다.

2. 가방은 오름차순 정렬을 시행해준다.

3. 가격이 높은 보석을 차례대로 보석 무게와 비슷한 가방을 찾아서 넣어준다(보석 가격 누적계산)

 

*우선순위 큐를 구현하여 사용한 예제

//우선순위 큐
class PriorityQueue {
  constructor() {
    this.store = [];
  }
  //무게와 가격을 받아서 배열에 넣어준다.
  enqueue(name, score) {
    this.store.push([name, score]);
  }
  //제일 큰 값을 리턴
  dequeue() {
    let entry = 0;
    this.store.forEach((item, index) => {
      if (this.store[entry][1] < this.store[index][1]) {
        entry = index;
      }
    });
    return this.store.splice(entry, 1);
  }
}

const solution = (k, priorityQueue, bag) => {
  let cnt = 0;
  //가방 개수 만큼
  for (let i = 0; i < k; i++) {
    //우선순위 큐에서 제일 큰 보석정보 가져옴
    let value = priorityQueue.dequeue();

    //가방을 순회하면서 보석 무게보다 크거가 같은 경우는 그 보석을 담았다고 가정하고
    //담은 가방을 제외한 가방을 리턴함
    bag = bag.map((el, index) => {
      if (el >= value[0][0]) {
        return;
      } else {
        return el;
      }
    });
    cnt += value[0][1];
  }
  console.log(cnt);
};

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];
rl.on("line", function (line) {
  //여러줄 입력
  input.push(line);
}).on("close", function () {
  let [n, k] = input
    .shift()
    .split(" ")
    .map((el) => Number(el));

  //우선순위 큐 생성
  const priorityQueue = new PriorityQueue();

  for (let i = 0; i < n; i++) {
    let [x, y] = input[i].split(" ").map((el) => Number(el));
    //우선순위 큐에 보석 무게, 가격 담아줌
    priorityQueue.enqueue(x, y);
  }
  let bag = [];
  //가방넣어줌
  for (let j = 0; j < k; j++) {
    bag.push(Number(input[j]));
  }
  //가방 오름차순정렬
  bag = bag.sort((a, b) => a - b);
  solution(k, priorityQueue, bag);
  process.exit();
});

 

 

* 문제 난이도가 높아질수록 우선순위 큐, 힙, 등등 자료구조를 이용해야지만 해결해야하는 문제들이 많아지는데 

이 문제 또한 우선순위 큐라는 자료구조를 이용해야지만 정답처리를 받을 수 있다. JS에서는 기본적인 자료구조가 제공되지 않아 우선순위 큐를 구현도 해보고 이런저런 시도를 통해 해결할려고 했지만 실패했다. (엄청난 실력자라면 가능할지라도 저는 실패했습니다.) JS는 다른언어들에 비해 자료구조가 한없이 부족한것 같다. 파이썬 처럼 모듈을 불러와 메소드처럼 사용할 수 있다면 얼마나 좋을까...