[알고리즘] 백준 11286 절대값 힙 node.js (heap)

항상 class를 이용해 메서드를 구현한 후 호출하는 방식은 언제나 낯설고 어렵다.

 

풀이 링크

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

 

풀이 방법

1. 힙 구현2. 절대값을 이용해 크기를 비교해야하기 때문에 체킹 필요

let [N, ...X] = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n")
  .map(Number);


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

    push(val) {
        this.heap.push(val);
        this._siftUp();
    }

    pop() {
        if (this.size() === 0) return 0;
        this._swap(0, this.size() - 1);
        const poppedValue = this.heap.pop();
        this._siftDown();
        return poppedValue;
    }

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

    _greater(a, b) {
        const absA = Math.abs(a), absB = Math.abs(b);
        if (absA === absB) return a > b;
        return absA > absB;
    }

    _swap(i, j) {
        [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
    }

    _siftUp() {
        let node = this.size() - 1;
        while (node > 0 && this._greater(this.heap[Math.floor((node - 1) / 2)], this.heap[node])) {
            this._swap(node, Math.floor((node - 1) / 2));
            node = Math.floor((node - 1) / 2);
        }
    }

    _siftDown() {
        let node = 0;
        while (
            (node * 2 + 1 < this.size() && this._greater(this.heap[node], this.heap[node * 2 + 1])) ||
            (node * 2 + 2 < this.size() && this._greater(this.heap[node], this.heap[node * 2 + 2]))
        ) {
            let minChild = (node * 2 + 2 < this.size() && this._greater(this.heap[node * 2 + 1], this.heap[node * 2 + 2])) ? node * 2 + 2 : node * 2 + 1;
            this._swap(node, minChild);
            node = minChild;
        }
    }
}

const pq = new MinHeap();
let result = [];

for (let i = 0; i < N; i++) {
    const n = X[i];
    if (n !== 0) {
        pq.push(n);
    } else {
        result.push(pq.pop());
    }
}

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

 

풀이 노트

 

---

클래스

객체 지향 프로그래밍에서 특정 객체를 생성하기 위해 변수와 메소드를 정의하는 일종의 틀로, 객체를 정의하기 위한 상태(멤버 변수)와 메서드(함수)로 구성된다.

Question !! 

그냥 '메소드'와 '_메소드'의 차이점

1. 명명 규칙:
   • 함수나 변수 이름 앞에 _를 붙이는 것은 해당 함수나 변수가 "프라이빗" 또는 "내부" 용도로 사용된다는 암묵적인 의미를 가진다.자바스크립트는 실제로 프라이빗 멤버를 지원하지 않기 때문에, _를 붙여서 외부에서 직접 접근하지 말아야 한다는 의미를 나타냄.
2. 일반적인 파이프라인 스타일:
   • _는 로대시(Lodash)나 언더스코어(Underscore.js) 라이브러리에서 함수형 프로그래밍 스타일을 지원하는 유틸리티 함수들의 네임스페이스로 사용된다. 예를 들어, _.map이나 _.filter 같은 함수 호출에서 _는 해당 라이브러리의 네임스페이스를 나타냄
3. 임시 변수:
   • 반복문이나 람다 표현식 등에서 사용되지 않는 변수에 _를 사용한다. 이는 해당 변수가 사용되지 않을 것임을 명확히 하는 데 도움이 됨.

여기서 _siftUp과 _siftDown 메서드는 MinHeap 클래스의 내부 메서드로, 외부에서 직접 호출하지 않도록 하기 위한 암묵적인 표시로 _를 사용한 예시이다.

 

function이 아닌 클래스로 짜는 이유

1. 구조화:
   • MinHeap 클래스 내에 힙과 관련된 모든 메서드(push, pop, _siftUp, _siftDown, _greater, _swap)가 포함되어 있어 힙의 동작을 명확하게 이해하고 유지할 수 있다. 이는 코드의 모듈화를 돕고, 객체 지향 프로그래밍의 장점을 활용할 수 있게 한다.
   • 함수 기반 접근법은 더 간단하고 직접적일 수 있지만, 관련된 데이터와 동작을 명시적으로 묶지 않습니다. 이는 코드의 가독성이나 유지보수성에서 차이를 만들 수 있다.
2. 재사용성:
   • MinHeap 클래스를 여러 알고리즘이나 프로그램에서 인스턴스화하여 사용할 수 있다. 예를 들어, 여러 종류의 우선순위 큐가 필요한 다양한 문제에서 재사용할 수 있다.
   • 함수 기반 접근법에서도 함수를 재사용할 수 있지만, 여러 개의 힙을 동시에 사용해야 하는 경우 클래스를 사용하는 것이 더 간단하다.
3. 유지보수성:
   • 힙의 동작을 수정해야 할 때, MinHeap 클래스 내의 메서드만 수정하면 됩니다. 다른 곳에서 이 클래스를 사용하는 코드에는 영향을 미치지 않는다.
   • 함수 기반 접근법에서는 관련된 함수들이 전역적으로 존재하기 때문에, 유지보수 시 더 많은 주의가 필요할 수 있다.
   • 클래스의 메서드들은 클래스의 인스턴스 내에 존재하므로, 전역적으로 존재하지 않습니다. 이는 클래스의 주요 장점 중 하나로, 네임스페이스 충돌을 피하고 코드의 모듈화를 촉진한다.
4. 상속과 다형성:
   • 다른 종류의 힙 (예: 최대 힙)을 만들고 싶다면, MinHeap 클래스를 상속받아 필요한 메서드만 재정의할 수 있다.
   • 함수 기반 접근법에서는 이러한 상속 및 다형성을 직접적으로 제공하지 않기 때문에, 동일한 기능을 구현하기 위해 더 많은 코드가 필요할 수 있다.

결론적으로, 함수로도 구현할 수 있지만, 클래스는 코드의 구조화, 재사용성, 유지보수성 측면에서 더 많은 이점을 제공한다.