Node.js) BOJ 11286번 : 절댓값 힙

 

const [_, ...input] = fs.readFileSync(filepath).toString().trim().split("\n");

위와 같은 표현식이 낯설었다. 이렇게 쓴 이유는 인자를 받을 때 처음 받는 인자는 불필요하여 버릴때 위와 같이 배열 안에 언더바를 사용할 수 있다.

input은 내가 입력한 데이터를 포함한 개행문자까지 모두 포함되고 거기에 추가로 배열의 형식인 쉼표 까지 추가된다. 예를들어 이 문제의 초기 입력 데이터가 

와 같을 때 input에 들어간 값을 console.log로 확인해 보면

와 같음을 확인할 수 있다(아래 코드에 모든거 남겨놓았다). 그리고 이것을

const num = input.map(v => +v);

한 결과 num을 출력해 보면

num: 1,-1,0,0,0,1,1,-1,-1,2,-2,0,0,0,0,0,0,0num의 타입: object

 

이 출력되는 것을 확인할 수 있다. 즉 num은 내가 실제로 문제를 풀기위해 사용되는 순수 배열인 것이다.

 

const fs=require('fs');
const filepath=process.platform==='linux'?'dev/stdin':'./input.txt';
const [_, ...input] = fs.readFileSync(filepath).toString().trim().split("\n");

// console.log("input: "+input+"input의 타입: "+typeof(input));
const num = input.map(v => +v);
// console.log("num: "+num+"num의 타입: "+typeof num);

class AbsoluteMinHeap {
  constructor() {
    this.heap = [];
  }

  empty() {
    if (this.heap.length == 0) {
      return true;
    }
    return false;
  }

  swap(arr, x, y) {
    // let temp = arr[x];
    // arr[x] = arr[y];
    // arr[y] = temp;
    // return;
    [arr[x],arr[y]]=[arr[y],arr[x]]//쌉가능
  }

  //[절대값, 원래값]으로 넣어줄 에정. 

  insert(value) {
    this.heap.push(value);
    this.bubbleUp();
  }

  bubbleUp() {
    let currentIndex = this.heap.length - 1;

    while (currentIndex > 0) {
      const parentIndex = Math.floor((currentIndex - 1) / 2);
      if (this.heap[parentIndex][0] < this.heap[currentIndex][0]
        || (this.heap[parentIndex][0] == this.heap[currentIndex][0] && this.heap[parentIndex][1] < this.heap[currentIndex][1])) {
        break;
      }
      this.swap(this.heap, parentIndex, currentIndex)
      currentIndex = parentIndex;
    }
  }


  extractMin() {
    if (this.heap.length == 1) {
      return this.heap.pop();
    }
    const min = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.sinkDown(0);
    return min
  }

  sinkDown(index) {
    const leftIndex = 2 * index + 1;
    const rightIndex = 2 * index + 2;
    const length = this.heap.length;
    let smallestIndex = index;

    if (leftIndex < length && (this.heap[leftIndex][0] < this.heap[smallestIndex][0]
      || (this.heap[leftIndex][0] == this.heap[smallestIndex][0]) && this.heap[leftIndex][1] < this.heap[smallestIndex][1])
    ) {
      smallestIndex = leftIndex;
    }
    if (rightIndex < length && (this.heap[rightIndex][0] < this.heap[smallestIndex][0]
      || (this.heap[rightIndex][0] == this.heap[smallestIndex][0]) && this.heap[rightIndex][1] < this.heap[smallestIndex][1])
    ) {
      smallestIndex = rightIndex;
    }
    if (smallestIndex !== index) {
      this.swap(this.heap, index, smallestIndex);
      this.sinkDown(smallestIndex)
    }
  }
}

const answer = [];
const maxHeap = new AbsoluteMinHeap();
num.forEach(v => {
  if (v == 0) {
    if (maxHeap.empty()) {
      answer.push(0);
    } else {
      answer.push(maxHeap.extractMin()[1]);
    }
  } else {
    maxHeap.insert([Math.abs(v), v]);
  }
})

console.log(answer.join('\n'));