[Algorithm]Baekjun中間-最大臀部、最小臀部探索バイナリ

真ん中を言う

白俊-真ん中で解くって
中間値を求める問題は、数を1つ増やすごとにsort()の方法で中間値を求めた結果、メモリが超過した.時間の制限や空間の制限が迫っているため、別の道を切り開かざるを得ない.そこで選択した方法は,最大ヒップ,最小ヒップを用いた方法であり,その後,バイナリ検索により並べ替えを常に維持する方法で行った.

最大お尻、最小お尻で問題を解決

前回のPostingでは最大ヒップ最小ヒップを自ら体現の問題を解決するために、いくつかの点を書き直し、補足しました.

class Heap {
  constructor(comparator = (lhs, rhs) => lhs < rhs) {
    this.heap = [0];
    this._comparator = comparator;
  }

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

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

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

  size() {
    return this.heap.length - 1;
  }

  insert(data) {
    this.heap.push(data);
    const moveUp = (index = this.heap.length - 1) => {
      const parentIndex = Math.floor(index / 2);
      if (index === 1 || !this._comparator(this.heap[index], this.heap[parentIndex])) return;
      this.swap(index, parentIndex);
      moveUp(parentIndex);
    };
    moveUp();
  }

  extract() {
    if (this.empty()) return;
    if (this.size() === 1) return this.heap.pop();
    const data = this.heap[1];
    this.heap[1] = this.heap.pop();
    const moveDown = (index = 1) => {
      const leftChildIndex = index * 2;
      const rightChildIndex = index * 2 + 1;
      if (leftChildIndex >= this.heap.length) return 0;
      if (rightChildIndex >= this.heap.length) {
        if (this._comparator(this.heap[leftChildIndex], this.heap[index])) {
          this.swap(leftChildIndex, index);
          moveDown(leftChildIndex);
        }
      } else {
        if (this._comparator(this.heap[leftChildIndex], this.heap[rightChildIndex])) {
          if (this._comparator(this.heap[leftChildIndex], this.heap[index])) {
            this.swap(leftChildIndex, index);
            moveDown(leftChildIndex);
          }
        } else {
          if (this._comparator(this.heap[rightChildIndex], this.heap[index])) {
            this.swap(rightChildIndex, index);
            moveDown(rightChildIndex);
          }
        }
      }
    };
    moveDown();
    return data;
  }
}

heapの作成時に、最大hipと最小hipを区別するためにcomparatorを追加し、Heapと命名した.大きさを比較するためにsize()を増やし、値を取り出すのではなく確認できるpeek()だけを増やした.
次は問題解決コードです.

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

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

/**
 * 최대힙과 최소힙을 활용하여 중간값을 얻는다.
 *
 * >> 최대힙의 최댓값이 최소힙의 최솟값보다 항상 작거나 같게 유지를 하면, 최대힙의 최댓값이 항상 중간값이 된다.
 *
 * [ 1, 5, 2, 10, -99, 7, 5 ]
 *   최대힙 최소힙
 * 1: [1], [] => 최소힙이 empty라면 최대힙을 중간값으로 한다. (1)
 * 5: [1], [5] => 두 사이즈가 같으므로 최대힙의 최대를 중간값으로 한다. (1)
 * 2: [2, 1], [5] => 최대힙보다 최소힙이 항상 더 작게 유지해야하므로 2를 최대힙으로 옮긴다. (2)
 * 10: [2, 1], [5, 10] => 최대힙의 최대가 최소힙의 최소보다 작으므로 2를 중간값으로 한다.
 * -99: [2, 1, -99], [5, 10] => 위와 같다. (2)
 * 7: [2, 1, -99], [5, 7, 10] => 위와 같다. (2)
 * 5: [5, 2, 1, -99], [5, 7, 10] => 5는 최소힙의 최소와 같으므로 최대힙의 최대가 된다. (5)
 *
 * @param {number[]} numbers 수빈이가 외치는 정수
 * @return 수빈이의 동생이 말해야 하는 수
 */
function solution(numbers) {
  const maxHeap = new Heap((lhs, rhs) => lhs > rhs);
  const minHeap = new Heap();

  return numbers
    .map((number) => {
      maxHeap.size() === minHeap.size() ? maxHeap.insert(number) : minHeap.insert(number);
      if (maxHeap.peek() > minHeap.peek()) {
        const temp = minHeap.extract();
        minHeap.insert(maxHeap.extract());
        maxHeap.insert(temp);
      }
      console.log(maxHeap.heap, minHeap.heap);
      return maxHeap.peek();
    })
    .join("\n");
}

// ... Declaration of Heap Class

const lines = [];
reader
  .on("line", (line) => {
    lines.push(line.trim());
  })
  .on("close", () => {
    const N = Number(lines.shift());
    const numbers = lines.map(Number);
    console.log(solution(numbers));
    process.exit();
  });

lhsとrhsの大きさの比較により、最大臀部と最小臀部を区別することができる.基本パラメータは最小hipで実現した.

const maxHeap = new Heap((lhs, rhs) => lhs > rhs);
const minHeap = new Heap();

numbersを巡り、最大ヒップと最小ヒップに数字を追加します.

차례대로 부를 수: 1 15 5 3 2 -99 7 5
최대힙 & 최소힙: [] []
중간값 {}
# 매번 반복에서 최대 힙의 최댓값이 중간값이 된다.

1. 최대힙과 최소힙의 사이즈가 같으면 최대힙에 숫자 추가, 다르면 최소힙에 숫자 추가
2. 최대힙의 최댓값이 최소힙의 최솟값보다 크다면, 두 값을 스왑한다.
3. 최대힙의 최댓값이 중간값이 되므로 이를 반환한다.

1: {1}
사이즈 같음: [1] []
최소힙 없음

15: {1}
사이즈 다름: [1] [15]
최솟값이 더 큼

5: {5}
사이즈 같음: [5, 1] [15]
최솟값이 더 큼

3: {3}
사이즈 다름: [5, 1] [3, 15]
최댓값이 더 큼: [3, 1] [5, 15]

2: {3}
사이즈 같음: [3, 2, 1] [5, 15]
최솟값이 더 큼

-99: {2}
사이즈 다름: [3, 2, 1] [-99, 5, 15]
최댓값이 더 큼: [2, 1, -99] [3, 5, 15]

7: {3}
사이즈 같음: [7, 2, 1, -99] [3, 5, 15]
최댓값이 더 큼: [3, 2, 1, -99] [5, 7, 15]

5: {3}
사이즈 다름: [3, 2, 1, -99] [5, 5, 7, 15]
최솟값이 더 큼

최종적으로 1 1 5 3 3 2 3 3 가 출력된다.

return numbers
  .map((number) => {
    maxHeap.size() === minHeap.size() ? maxHeap.insert(number) : minHeap.insert(number);
    if (maxHeap.peek() > minHeap.peek()) {
      const temp = minHeap.extract();
      minHeap.insert(maxHeap.extract());
      maxHeap.insert(temp);
    }
    return maxHeap.peek();
  })
  .join("\n");

バイナリ・ナビゲーションを使用して問題を解決

バイナリサーチにより毎回昇順を保つように行い,O(Nlogn)O(Nlogn)O(Nlogn)O(Nlogn)を用いて問題を解決することができる.

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

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

/**
 * 이진탐색을 활용하여 항상 오름차순을 유지한다. 중간값을 출력한다.
 * [ 1, 5, 2, 10, -99, 7, 5 ]
 *
 * [-99, 1, 2, 5, 10] <- 7
 *
 * left = 0; right = arr.length - 1; mid = Math.floor((left + right) / 2);
 * => left = 0;, right = 4; mid = 2;
 *
 * arr[mid]가 7보다 작으므로 left = mid + 1;
 * => left = 3; right = 4; mid = 3
 *
 * arr[mid]가 7보다 작으므로 left = mid + 1;
 * => left = 4; right = 4; mid = 4
 *
 * arr[mid]가 7과 같으므로 arr.splice(mid, 0, 7)로 배열에 값 추가
 *
 * @param {number[]} numbers 수빈이가 외치는 정수
 * @return 수빈이의 동생이 말해야 하는 수
 */
function solution(numbers) {
  const arr = [];
  return numbers
    .map((number) => {
      let left = 0;
      let right = arr.length - 1;
      while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (arr[mid] <= number) left = mid + 1;
        else right = mid - 1;
      }
      arr.length ? arr.splice(left, 0, number) : arr.push(number);
      const mid = Math.floor(arr.length / 2);
      if (arr.length % 2) return arr[mid];
      return arr[mid - 1];
    })
    .join("\n");
}

const lines = [];
reader
  .on("line", (line) => {
    lines.push(line.trim());
  })
  .on("close", () => {
    const N = Number(lines.shift());
    const numbers = lines.map(Number);
    console.log(solution(numbers));
    process.exit();
  });

配列の特定のインデックスに値を挿入するには、spliceメソッドを使用します.最悪の場合、O(N)O(N)O(N)O(N)の時間的複雑さが必要となる.
次は最大ヒップ/最小ヒップで解決する問題で、上はバイナリ検索で解決する問題です.