백준 1655 < 가운데를 말해요 > JavaScript

📍문제 링크

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

1655번: 가운데를 말해요

 

📍알고리즘 분류

- 자료 구조

- 우선순위 큐

 

📍문제 풀이

1 <= N <= 100,000  이고

N 개의 숫자 (-10,000 이상 10,000 이하의 정수)가 한 줄씩 주어질 때 중위값 구하기

 

naive하게 숫자가 추가될 때마다 정렬하여 중위값을 구하면 되지만.. 이 때 시간 복잡도가 N * N logN 이 되어버린다

이 문제에서는 시간 제한이 0.1초라서 절대 불가능하다

 

중위값에 대해서 깊게 생각해보면.. 중간 인덱스에 위치한 원소이다

- N 이 홀수 일때는 floor(N / 2) 이고

- N 이 짝수 일때는 N / 2

 

그림을 그려보면

 

중위값을 제외한 큰수그룹(오렌지)과 작은수그룹(노란색) 으로 나눌 수 있다

잘 살펴보면 큰수그룹의 최솟값과 작은수그룹의 최댓값 사이에서 중위값이 결정된다

 

중위값을 작은수그룹으로 편입하고, 작은수그룹의 최댓값이라고 하면 어떨까?

 

이러면 N이 1일 때도 답을 구할 수 있다

 

시뮬레이션을 해보자

 

 

⭐작은수그룹의 최댓값이 중위값!

현재 중위값을 기준으로 큰 수가 들어오면 큰수그룹에 보내고 정렬

작은 수가 들어오면 작은수 그룹에 들어오고 정렬

 

N = 3일때 2가 들어오는데, 2는 일단 큰수그룹으로 이동.

이때, 큰수 그룹의 길이가 작은수그룹의 길이보다 크면 큰수그룹의 최솟값을 작은수그룹으로 보냄

그결과가 사진의 N=3

 

N =  5일때 만약 -100이 들어와서 작은수로 넣었는데, 작은수그룹의 길이가 큰수그룹의 길이보다 2 커진다

이때는 작은수그룹의 최댓값(현재중위값)을 큰수그룹으로 보내기

 

⭐이러면 로직은 완성됐고, 배열에서 최대, 최소값을 빠르게 구하기 위해 이진힙을 사용하면 된다!

큰수그룹 = 최소힙

작은수그룹 = 최대힙 (여기의 루트가 중위값)

 

📍코드 (JavaScript)

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

const input = [];
// 큰수그룹
class MinHeap {
  constructor() {
    this.values = [];
  }

  getLen() {
    return this.values.length;
  }

  enqueue(val) {
    this.values.push(val);
    this.bubbleUp();
  }

  bubbleUp() {
    let idx = this.values.length - 1;
    const element = this.values[idx];
    while (idx > 0) {
      let parentIdx = Math.floor((idx - 1) / 2);
      let parent = this.values[parentIdx];
      if (element >= parent) break;
      this.values[parentIdx] = element;
      this.values[idx] = parent;
      idx = parentIdx;
    }
  }

  dequeue() {
    const min = this.values[0];
    const end = this.values.pop();
    if (this.values.length > 0) {
      this.values[0] = end;
      this.sinkDown();
    }
    return min;
  }

  sinkDown() {
    let idx = 0;
    const length = this.values.length;
    const element = this.values[0];
    while (true) {
      let leftIdx = 2 * idx + 1;
      let rightIdx = 2 * idx + 2;
      let left, right;
      let swap = null;
      if (leftIdx < length) {
        left = this.values[leftIdx];
        if (left < element) {
          swap = leftIdx;
        }
      }
      if (rightIdx < length) {
        right = this.values[rightIdx];
        if (
          (swap === null && right < element) ||
          (swap !== null && right < left)
        ) {
          swap = rightIdx;
        }
      }
      if (swap === null) break;
      this.values[idx] = this.values[swap];
      this.values[swap] = element;
      idx = swap;
    }
  }
}

// 작은수그룹
class MaxHeap {
  constructor() {
    this.values = [];
  }

  getLen() {
    return this.values.length;
  }

  enqueue(val) {
    this.values.push(val);
    this.bubbleUp();
  }

  bubbleUp() {
    let idx = this.values.length - 1;
    const element = this.values[idx];
    while (idx > 0) {
      let parentIdx = Math.floor((idx - 1) / 2);
      let parent = this.values[parentIdx];
      if (element <= parent) break;
      this.values[parentIdx] = element;
      this.values[idx] = parent;
      idx = parentIdx;
    }
  }

  dequeue() {
    const max = this.values[0];
    const end = this.values.pop();
    if (this.values.length > 0) {
      this.values[0] = end;
      this.sinkDown();
    }
    return max;
  }

  sinkDown() {
    let idx = 0;
    const length = this.values.length;
    const element = this.values[0];
    while (true) {
      let leftIdx = 2 * idx + 1;
      let rightIdx = 2 * idx + 2;
      let left, right;
      let swap = null;
      if (leftIdx < length) {
        left = this.values[leftIdx];
        if (left > element) {
          swap = leftIdx;
        }
      }
      if (rightIdx < length) {
        right = this.values[rightIdx];
        if (
          (swap === null && right > element) ||
          (swap !== null && right > left)
        ) {
          swap = rightIdx;
        }
      }
      if (swap === null) break;
      this.values[idx] = this.values[swap];
      this.values[swap] = element;
      idx = swap;
    }
  }
}

rl.on("line", (line) => {
  input.push(+line);
}).on("close", () => {
  const N = input[0];
  const minHeap = new MinHeap();
  const maxHeap = new MaxHeap();
  const answer = [input[1]];
  maxHeap.enqueue(input[1]);
  for (let i = 2; i <= N; i++) {
    if (input[i] > maxHeap.values[0]) minHeap.enqueue(input[i]);
    else maxHeap.enqueue(input[i]);

    // 큰수그룹의 길이가 작은수그룹의 길이보다 커지면
    // 큰수그룹의 최솟값(최소힙의 루트)을 작은수그룹으로 보낸다 (중위값 변경)
    if (minHeap.getLen() > maxHeap.getLen()) {
      maxHeap.enqueue(minHeap.dequeue());
      // 작은수그룹의 길이가 큰수그룹의 길이보다 2개 많으면
      // 작은수그룹의 최댓값(최대힙의 루트, 현재중위값)을 큰수그룹으로 보낸다 (중위값 변경)
    } else if (minHeap.getLen() + 1 < maxHeap.getLen()) {
      minHeap.enqueue(maxHeap.dequeue());
    }
    answer.push(maxHeap.values[0]);
  }
  console.log(answer.join("\n"));
});