[JavaScript] 백준 코딩테스트 : 최대 힙

📌  문제

널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

1. 배열에 자연수 x를 넣는다.
2. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

📌  입력 및 출력

• 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 231보다 작다.
• 입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 큰 값을 출력하라고 한 경우에는 0을 출력하면 된다.

📌  예제 입력 및 출력

---

📌  풀이

알아야 하는 것

• 입력값 받기
• 자료구조 힙 Heap - 최대 힙

구할 것

• 아직 힙을 구현할 줄 몰라서 다른 분들이 구현하신 코드를 보고 이해하는 것부터 했다.
• 코드를 하나씩 풀이하면서 이해해보고 직접 구현해보기로 했다.

[코딩테스트]백준 - 최대 힙(11279)

 

1. 백준에서 입력값 받기

백준은 프로그래머스와 달리 입력 받을 데이터를 정제화 해줘야 한다. 특히 이번 문제처럼 여러 개의 값이 여러 줄로 출력될 경우는 아래와 같이 출력해 받아야 한다. 먼저 fs 모듈을 불러와야 하는데, 이것은 Node.js에서 파일 입출력 처리를 할 때 사용된다. 모듈을 불러온 후 toString과 trim을 사용해 문자열로 만들어 양쪽 공백을 제거한다. 그리고 개행을 기준으로 나눠주는 게 여러 개의 값을 여러 줄로 출력할 때 기본 포맷이다.

 

백준에서 문제를 풀어 제출할 때는 readFileSync에 '/dev/stdin'를 입력하면 된다. 나처럼 VSC에서 풀어볼 사람은 별도로 input.txt 파일을 만들어 아래와 같이 입력값을 적어두면 된다. 

 

let fs = require("fs");
var input = fs.readFileSync("./input.txt").toString().trim().split("\n");

2. 시작

현재 input은 ['13', '0', '1', '2', '0', '0', '3', '2', '1', '0', '0', '0', '0', '0'] 형태로 데이터가 담겨 있다.

0번째 인덱스는 입력 데이터의 갯수고 1번째 인덱스부터 진짜 입력 데이터이므로 1부터 for문을 돌아 push하되 필요한 값은 숫자라 다시 Number로 바꿔준다. (왜... 인지 모르겠다?) 

let operations = [];
for (let i = 1; i < input.length; i++) {
  operations.push(Number(input[i]));
}

 

먼저 힙을 구현한 후 진짜 코드는 아래와 같다. maxHeap은 최대힙을 말하고, 인스턴스를 만들었다. 추출한 값을 저장할 변수 extracts를 선언하고, operations를 순회한다.

 

이 때 0이 아니라면 데이터는 빈 배열인 operation에 삽입된다. 만약 0이라면 1) 힙의 길이가 0으로 출력할 것이 없을 경우 그대로 0을 출력 (문제에 배열이 비어 있는 경우 가장 큰 값을 출력하라고 한다면 0을 출력하라고 함) 2) 가장 큰 값을 t에 할당한 후 개행과 함께 추가한다.

 

이러면 예제 출력처럼 한 줄마다 데이터가 나오고, 공백을 없애주기 위해 trim을 사용해 양쪽 공백을 지워준다.

const heap = new maxHeap();
let extracts = "";

operations.forEach((operation) => {
  if (operation !== 0) {
    heap.insert(operation);
  } else {
    if (heap.nodes.length === 0) {
      extracts += "0" + "\n";
    } else {
      let t = heap.extract();
      extracts += t + "\n";
    }
  }
});

console.log(extracts.trim())

 

3. 최대 힙 구현하기

maxHeap이라는 클래스를 정의하고 클래스의 생성자 함수를 정의한다.

this.nodes = []는 nodes 라는 빈 배열을 생성해 현재 힙의 노드들을 저장할 때 사용할 거다.

 

힙에서는 데이터가 들어올 때 가장 맨 밑에서부터 들어온다. 따라서 push로 데이터를 배열의 맨 오른쪽에 삽입한 후 bubbleUp() 함수를 실행한다. 최대 힙을 구현하기 위해서 해당 데이터의 값이 부모 노드의 값보다 크다면 위로 올라가야 하기 때문이고, 이러한 교환행위를 버블이라고 한다.

class maxHeap {
  constructor() {
    this.nodes = [];
  }

  insert(data) {
    this.nodes.push(data);
    this.bubbleUp();
  }

 

bubbleUp() 함수가 실행될 때 기준은 가장 맨 밑에서 시작한다. 이 때 만약 인덱스가 0이라면 들어온 노드가 루트 노드가 되기 때문에 비교할 부모 노드나 자식 노드가 없어 그대로 함수가 종료된다. 그렇지 않을 경우 currentNode는 현재 노드의 인덱스, 즉 가장 끝이 된다. 이 때 부모 노드의 인덱스는 (현재 인덱스 - 1) / 2로 계산되는데 정수형으로 반환하기 위해서 Math.floor로 소수점을 버린다. 그렇게 부모 노드의 인덱스와 값을 구했을 때, 부모 노드가 현재 노드보다 크거나 같다면 최대 힙을 구현하고 있기 때문에 함수는 또 그대로 종료된다.

 

만약 부모 노드보다 현재 노드가 클 경우에는 교환을 해줘야 한다. 그래서 부모 노드의 인덱스와 현재 노드의 인덱스를 바꾸고, 부모 노드의 값과 현재 노드의 값을 바꾼 후 업데이트된 인덱스로 bubbleUp() 을 재귀적으로 호출한다. (계속해서 올라가야 하니까)

 

bubbleUp(index = this.nodes.length - 1) {
    if (index < 1) return;
    // 인덱스가 0 === 루트 노드면 그대로 리턴

    let currentNode = this.nodes[index];
    let parentIndex = Math.floor((index - 1) / 2);
    let parentNode = this.nodes[parentIndex];

    if (parentNode >= currentNode) return;
    // 부모 노드가 현재 노드보다 크거나 같으면 그대로 리턴

    // 현재 노드가 부모 노드보다 크면 바꿔서 올라가기
    this.nodes[parentIndex] = currentNode;
    this.nodes[index] = parentNode;
    index = parentIndex;
    this.bubbleUp(index);
    // 부모 인덱스로 호출
  }

 

최대 값의 노드를 추출할 때는 아래와 같이 진행된다. 현재 노드의 최상단(배열의 0번째 인덱스)가 상수 max가 된다. 만약 루트 노드가 최대 값의 노드라면 그대로 0번째 노드를 pop으로 꺼내고 해당 값을 리턴한다.

 

하지만 배열에 루트 노드 말고 다른 노드들이 있다면 최대 값의 노드 추출 후 비교를 해 빈 자리를 또 채워줘야 한다. 따라서 우선 최대 값의 노드를 추출한 후 trickleDown()을 실행한다.

 

// max노드 추출하기
  extract() {
    const max = this.nodes[0];

    // 루트 노드가 1개라면 그대로 추출
    if (this.nodes.length === 1) {
      this.nodes.pop();
      return max;
    }

    // 루트 노드가 1개가 아니면 추출 후 맨 아래 노드가 맨 위로 올라오게 하기
    this.nodes[0] = this.nodes.pop();
    this.heapifyDown();
    return max;
  }

 

trickleDown()은 0번째 인덱스를 기준으로 시작한다. 부모 노드의 인덱스를 계산했던 것과 반대로 계산하여 왼쪽 자식 노드 인덱스와 오른쪽 자식 노드 인덱스를 계산한다. 최대 값의 노드가 추출되었으니 그 다음 최대 값의 노드(2순위였을 === 현재 0번째인)가 maximum으로 시작된다.

 

만약 왼쪽 자식 노드도 없고 오른쪽 자식 노드도 없다면 현재 0번째 인덱스가 최대 값의 노드이므로 그대로 종료된다. 만약 왼쪽 자식 노드만 있고, 현재 0번째 노드 값과 왼쪽 자식 노드 값을 비교했을 때 왼쪽 자식 노드 값이 더 크다면 이제 왼쪽 자식 노드가 올라가야 하기 때문에 maximum은 왼쪽 자식 노드의 인덱스로 바뀌게 된다. (오른쪽 자식만 있을 경우는 없기 때문에 제외한다.)

 

그런데 만약 왼쪽 자식 노드도 있고 오른쪽 자식 노드도 있다면 자식 노드들끼리 비교를 해야 한다. 이 때 오른쪽 자식 노드의 값이 더 크다면, 먼저 오른쪽 자식 노드가 유효한 범위인지 확인해야 한다. (기존 인덱스에서 2 곱하고 더했으니 현재 노드 배열의 값을 벗어났을 수도 있다.) 비교 후 동일하게 오른쪽 자식 노드가 더 클 경우 maximum은 해당 자식의 인덱스로 바뀐다. 왼쪽 자식 노드가 더 크고 유효한 범위일 때도 동일하게 maximum은 해당 자식의 인덱스로 바뀐다.  

 

heapifyDown(index = 0) {
    let leftChildIndex = index * 2 + 1;
    let rightChildIndex = index * 2 + 2;
    let length = this.nodes.length;
    let maximum = index; // maximum = 0

    // 왼쪽 자식 노드도 없고 오른쪽 자식 노드도 없을 때 max만 리턴한 채 현재 함수는 종료
    if (!this.nodes[leftChildIndex] && !this.nodes[rightChildIndex]) return;

    // 왼쪽 자식 노드만 있을 때 비교해서 최대 인덱스는 왼쪽 자식 인덱스
    if (!this.nodes[rightChildIndex]) {
      if (this.nodes[leftChildIndex] > this.nodes[maximum]) {
        maximum = leftChildIndex;
      }
    }

    // 왼쪽 자식 노드와 오른쪽 자식 노드 모두 있을 때, 오른쪽 자식 노드가 더 크다면
    if (this.nodes[leftChildIndex] < this.nodes[rightChildIndex]) {
      if (
        // 오른쪽 자식 노드가 유효한 범위 내에 있는지 확인 후 최대 인덱스는 오른쪽 자식 인덱스
        rightChildIndex <= length &&
        this.nodes[rightChildIndex] > this.nodes[maximum]
      ) {
        maximum = rightChildIndex;
      }
    } else {
      // 왼쪽 자식 노드가 더 크다면 동일하게 유효 범위 확인 후 최대 인덱스는 왼쪽 자식 인덱스
      if (
        leftChildIndex <= length &&
        this.nodes[leftChildIndex] > this.nodes[maximum]
      ) {
        maximum = leftChildIndex;
      }
    }

 

만약 maximum이 index(0으로 시작했으며 현재 최대 값의 노드임)이 아니라면 교환을 해야 한다. 임시 변수 t에 자식 노드의 값을 할당한 후, 현재 노드의 위치에 자식 노드의 인덱스 값을 대입해 현재 노드의 값을 자식 노드의 값으로 변경한다. 그리고 자식 노드의 위치에는 현재 노드의 값을 대입해 교환을 완료한다.

 

이후 trickleDown() 을 재귀적으로 호출해서 자식 노드로 이동한 현재 노드를 다른 자식 노드들과 다시 비교하게 한다. 

// 만약 최대 인덱스가 0이 아니라면 더 큰 노드의 값을 t에 할당
    if (maximum !== index) {
      let t = this.nodes[maximum];
      // 현재 노드 위치에 자식 노드 인덱스 값을 대입 === t
      this.nodes[maximum] = this.nodes[index];
      this.nodes[index] = t;
      this.heapifyDown(maximum);
    }

 

예제로 간략하게 확인해보자.

['13', '0', '1', '2', '0', '0', '3', '2', '1', '0', '0', '0', '0', '0']

 

1. 0

heap.nodes.length가 0이라서 extracts에 0과 개행이 더해졌다.

 

2. 1

heap.insert(operation)이 실행된다. operation = [1] 이 되고, bubbleUp()이 실행되지만 인덱스가 0, 곧 루트 노트가 되기 때문에 비교할 대상이 없어 그대로 종료된다.

 

3. 2

heap.insert(operation)이 실행된다. operation = [1, 2]가 되었다. bubbleUp()이 실행된다. 현재 노드(1번째 인덱스 === 2)가 부모 노드보다 크기 때문에 교환이 진행된다. 이후 재귀적으로 bubbleUp()이 실행되지만 [2, 1]로 바뀐 상태이며 현재 노드가 부모 노드보다 작기 때문에 교환이 진행되지 않고 그대로 종료된다.

 

4. 0

최대값을 추출한다. extract()가 실행된다. max는 현재 operation의 0번째 인덱스인 2로, pop 된 후 heapifyDown()이 실행된다. operation = [1]로 왼쪽 자식 노드도 없고 오른쪽 자식 노드도 없기 때문에 max만 리턴한 채 함수는 종료된다.

 

5. 0

최대 값을 추출한다. extract()가 실행된다. max는 현재 operation의 0번째 인덱스인 1로, pop된 후 그대로 종료된다. 이로써 operation은 빈 배열이 됐다.

 

6. 3

heap.insert(operation)이 실행된다. operation = [3] 이 되고, bubbleUp()이 실행되지만 인덱스가 0, 곧 루트 노트가 되기 때문에 비교할 대상이 없어 그대로 종료된다.

 

7. 2

heap.insert(operation)이 실행된다. operation = [3, 2] 이 되고, bubbleUp()이 실행되지만 부모 노드가 현재 노드보다 크기 때문에 교환이 진행되지 않고 그대로 종료된다.

 

8. 1

heap.insert(operation)이 실행된다. operation = [3, 2, 1] 이 되고, bubbleUp()이 실행되지만 부모 노드가 현재 노드보다 크기 때문에 교환이 진행되지 않고 그대로 종료된다.

 

9. 0

최대 값을 추출한다. extract()가 실행된다. max는 현재 operation의 0번째 인덱스인 3으로, pop 된 후 heapifyDown()이 실행된다. operation = [2, 1]로 현재 왼쪽 자식 노드만 존재한다. 왼쪽 자식 노드와 비교했을 때 maximum은 현재 인덱스이므로 더 이상의 교환은 일어나지 않는다.

 

10. 0

최대 값을 추출한다. extract()가 실행된다. max는 현재 operation의 0번째 인덱스인 2로, pop 된 후 heapifyDown()이 실행된다. operation = [1]로 왼쪽 자식 노드도 없고 오른쪽 자식 노드도 없기 때문에 max만 리턴한 채 함수는 종료된다.

 

11. 0

최대 값을 추출한다. extract()가 실행된다. max는 현재 operation의 0번째 인덱스인 1로, pop된 후 그대로 종료된다. 이로써 operation은 빈 배열이 됐다.

 

12. 0

배열은 비어 있어 추출할 수 없다. 그대로 0이 더해졌다.

 

13. 0

상동

 

extract는 아래와 같이 출력된다.

0

2

1

3

2

1

0

0

 

trim으로 앞뒤 공백을 제거하여 출력한다.

 

백준 제출 시 전체 코드

let fs = require("fs");
var input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

let operations = [];
for (let i = 1; i < input.length; i++) {
  operations.push(Number(input[i]));
}

class maxHeap {
  constructor() {
    this.nodes = [];
  }

  // 데이터가 들어오면 맨 밑에 넣고 실행
  insert(data) {
    this.nodes.push(data);
    this.bubbleUp();
  }

  // 인덱스는 맨 아래쪽
  bubbleUp(index = this.nodes.length - 1) {
    if (index < 1) return;
    // 인덱스가 0 === 루트 노드면 그대로 리턴

    let currentNode = this.nodes[index];
    let parentIndex = Math.floor((index - 1) / 2);
    let parentNode = this.nodes[parentIndex];

    if (parentNode >= currentNode) return;
    // 부모 노드가 현재 노드보다 크거나 같으면 그대로 리턴

    // 현재 노드가 부모 노드보다 크면 바꿔서 올라가기
    this.nodes[parentIndex] = currentNode;
    this.nodes[index] = parentNode;
    index = parentIndex;
    this.bubbleUp(index);
    // 부모 인덱스로 호출
  }

  // max노드 추출하기
  extract() {
    const max = this.nodes[0];

    // 루트 노드가 1개라면 그대로 추출
    if (this.nodes.length === 1) {
      this.nodes.pop();
      return max;
    }

    // 루트 노드가 1개가 아니면 추출 후 맨 아래 노드가 맨 위로 올라오게 하기
    this.nodes[0] = this.nodes.pop();
    this.heapifyDown();
    return max;
  }

  // 힙 유지를 위해 노드를 아래로 이동
  heapifyDown(index = 0) {
    let leftChildIndex = index * 2 + 1;
    let rightChildIndex = index * 2 + 2;
    let length = this.nodes.length;
    let maximum = index; // maximum = 0

    // 왼쪽 자식 노드도 없고 오른쪽 자식 노드도 없을 때 max만 리턴한 채 현재 함수는 종료
    if (!this.nodes[leftChildIndex] && !this.nodes[rightChildIndex]) return;

    // 왼쪽 자식 노드만 있을 때 비교해서 최대 인덱스는 왼쪽 자식 인덱스
    if (!this.nodes[rightChildIndex]) {
      if (this.nodes[leftChildIndex] > this.nodes[maximum]) {
        maximum = leftChildIndex;
      }
    }

    // 왼쪽 자식 노드와 오른쪽 자식 노드 모두 있을 때, 오른쪽 자식 노드가 더 크다면
    if (this.nodes[leftChildIndex] < this.nodes[rightChildIndex]) {
      if (
        // 오른쪽 자식 노드가 유효한 범위 내에 있는지 확인 후 최대 인덱스는 오른쪽 자식 인덱스
        rightChildIndex <= length &&
        this.nodes[rightChildIndex] > this.nodes[maximum]
      ) {
        maximum = rightChildIndex;
      }
    } else {
      // 왼쪽 자식 노드가 더 크다면 동일하게 유효 범위 확인 후 최대 인덱스는 왼쪽 자식 인덱스
      if (
        leftChildIndex <= length &&
        this.nodes[leftChildIndex] > this.nodes[maximum]
      ) {
        maximum = leftChildIndex;
      }
    }

    // 만약 최대 인덱스가 0이 아니라면 더 큰 노드의 값을 t에 할당
    if (maximum !== index) {
      let t = this.nodes[maximum];
      // 현재 노드 위치에 자식 노드 인덱스 값을 대입 === t
      this.nodes[maximum] = this.nodes[index];
      this.nodes[index] = t;
      this.heapifyDown(maximum);

    }
  }
}
const heap = new maxHeap();
let extracts = "";
operations.forEach((operation) => { 
// operations: [0, 1, 2, 0, 0, 3, 2, 1, 0, 0, 0, 0, 0]

  if (operation !== 0) {
    heap.insert(operation);
  } else {
    if (heap.nodes.length === 0) {
      extracts += "0" + "\n";
    } else {
      let t = heap.extract();
      extracts += t + "\n";
    }
  }
});

console.log(extracts.trim());