인프런 커뮤니티 질문&답변

실시간 정렬해야되는 문제들 보면 거의 무조건 힙구조도 같이 이용해야하는 문제들이여서..

자바스크립트로 풀때는 최소 빨라도 3~4분정도는..

요로코롬

Min이나 Max 힙 구조 만드는데 소요해야하고,

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

  push(value) {
    this.heap.push(value);
    let currentIndex = this.heap.length - 1;
    let parentIndex = Math.floor(currentIndex / 2);
    while (parentIndex !== 0 && value > this.heap[parentIndex]) {
      const temp = this.heap[parentIndex];
      this.heap[parentIndex] = value;
      this.heap[currentIndex] = temp;

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

  pop() {
    if (this.heap.length === 1) return;
    if (this.heap.length === 2) {
      return this.heap.pop();
    }

    const 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]
    ) {
      if (this.heap[leftIndex] < this.heap[rightIndex]) {
        const temp = this.heap[currentIndex];
        this.heap[currentIndex] = this.heap[rightIndex];
        this.heap[rightIndex] = temp;

        currentIndex = rightIndex;
      } else {
        const temp = this.heap[currentIndex];
        this.heap[currentIndex] = this.heap[leftIndex];
        this.heap[leftIndex] = temp;

        currentIndex = leftIndex;
      }

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

    return returnValue;
  }
}

심지어 문제 구조에서, 힙에 들어가야하는게 객체요소이면서, 객체의 어떤 Key 값에 따라서 실시간 정렬해야할 경우엔 여기서 또 out of index , key값 더 생각해서,

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

  isEmpty() {
    return this.heap.length === 1;
  }

  _swap(a, b) {
    [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
  }

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

    //
    while (parentIndex !== 0 && this.heap[parentIndex].key > value.key) {
      this._swap(parentIndex, currentIndex);

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

  pop() {
    if (this.isEmpty()) return;
    if (this.heap.length === 2) return this.heap.pop();

    const returnValue = this.heap[1];
    this.heap[1] = this.heap.pop();

    let currentIndex = 1;
    let leftIndex = 2;
    let rightIndex = 3;

    while (
      (this.heap[leftIndex] &&
        this.heap[currentIndex].key > this.heap[leftIndex].key) ||
      (this.heap[rightIndex] && this.heap[currentIndex].key > this.heap[rightIndex].key)
    ) {
      if (this.heap[rightIndex] === undefined) {
        this._swap(leftIndex, currentIndex);
        currentIndex = leftIndex;
      } else if (this.heap[rightIndex].key < this.heap[leftIndex].key) {
        this._swap(rightIndex, currentIndex);
        currentIndex = rightIndex;
      } else if (this.heap[rightIndex].key >= this.heap[leftIndex].key) {
        this._swap(leftIndex, currentIndex);
        currentIndex = leftIndex;
      }

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

    return returnValue;
  }
}

요로코롬 이렇게 힙구조 작성하는데만 4~5분 먹고, 그담 문제 풀이 본격적으로 시작할 수 있습니다..

파이썬의 deque 같은경우는 자바스크립트에선 Queue 구조 1분. 먹고

왜 사람들이 파이썬 코테로 많이 쓰는지 알겠네요..

ㄷㄷ;;

import heapq , 단 1초면 모듈 가져오고, 끝이네요.

코테에서 import 모듈 제한 없다면 진짜 무조건 파이썬이네요 ;;