백준22252 - 정보 상인 호석 (최대 힙, 해시) node.js

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

 

문제 해결 방식

고릴라(상인)의 이름이 모두 영문으로 주어지고, 각 상인에 따라 가진 정보들을 구분할 수 있어야 하기 때문에, 이름에 따라 해싱하는 과정을 먼저 거쳤다.

이후에는 해당 상인이 정보를 얻는 것인지 혹은 호석이가 정보를 구매하는 것인지에 따라 나누어, 정보를 얻는 경우에는 해당 상인의 해싱값에 맞게 최대 힙에 데이터를 적재했다. (호석이는 기본적으로 정보를 구매할 때, 정보의 크기가 큰 순으로 구매하기 때문에 구매 과정에서 이를 효율적으로 하기 위해서는 최대힙으로 구현해야 했다. 이때 node.js는 최대 힙 지원이 되지 않아 구글에서 타인이 구현한 최대 힙 소스 코드를 가져와썼다.)

그리고 만약 정보를 구매하는 경우에는 해당 상인에 해싱값에 맞는 최대 힙에서 정보의 가치가 큰 순으로 빼내어 결괏값에 추가해주는 과정을 거치며 로직을 완성했다.

 

전체 소스 코드

const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "입력.txt")
  .toString()
  .trim()
  .split("\n");

class MaxHeap {
  constructor() {
    this.heap = [null];
    this.cnt = 0;
  }

  heappush(value) {
    this.heap.push(value);
    this.cnt++;

    let currentIndex = this.heap.length - 1;
    let parentIndex = Math.floor(currentIndex / 2);

    while (parentIndex !== 0 && this.heap[parentIndex] < value) {
      const temp = this.heap[parentIndex];
      this.heap[parentIndex] = this.heap[currentIndex];
      this.heap[currentIndex] = temp;

      currentIndex = parentIndex;
      parentIndex = Math.floor(currentIndex / 2);
    }
  }

  heappop() {
    if (this.cnt !== 0) this.cnt--;
    if (this.heap.length === 2) return this.heap.pop();

    let returnValue = this.heap[1];
    this.heap[1] = this.heap.pop();
    let currentIndex = 1;
    let leftIndex = 2;
    let rightIndex = 3;

    while (
      this.heap[currentIndex] < this.heap[leftIndex] ||
      this.heap[currentIndex] < this.heap[rightIndex]
    ) {
      const temp = this.heap[currentIndex];

      if (this.heap[leftIndex] < this.heap[rightIndex]) {
        this.heap[currentIndex] = this.heap[rightIndex];
        this.heap[rightIndex] = temp;
        currentIndex = rightIndex;
      } else {
        this.heap[currentIndex] = this.heap[leftIndex];
        this.heap[leftIndex] = temp;
        currentIndex = leftIndex;
      }

      leftIndex = currentIndex * 2;
      rightIndex = leftIndex + 1;
    }

    return returnValue;
  }
  top() {
    return this.heap[1];
  }

  heapreturn() {
    return this.heap;
  }

  size() {
    return this.cnt;
  }
}

function solution(data) {
  data.shift();

  const table = {},
    pqTable = {};
  let result = 0;

  let idx = 1;
  data.forEach((el) => {
    const seller = el.split(" ")[1];
    if (!table[seller]) {
      pqTable[idx] = new MaxHeap();
      table[seller] = idx++;
    }
  });

  data.forEach((el) => {
    const [order, seller, cnt, ...arr] = el
      .split(" ")
      .map((el) => (!isNaN(el) ? Number(el) : el));

    if (order === 1) {
      arr.forEach((el) => {
        pqTable[table[seller]].heappush(el);
      });
    } else {
      for (let i = 0; i < cnt; i++) {
        if (!pqTable[table[seller]].size()) break;
        else result += pqTable[table[seller]].heappop();
      }
    }
  });

  console.log(result);
}

solution(input);