항상 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 !!
그냥 '메소드'와 '_메소드'의 차이점
- 명명 규칙:
- 함수나 변수 이름 앞에 _를 붙이는 것은 해당 함수나 변수가 "프라이빗" 또는 "내부" 용도로 사용된다는 암묵적인 의미를 가진다.자바스크립트는 실제로 프라이빗 멤버를 지원하지 않기 때문에, _를 붙여서 외부에서 직접 접근하지 말아야 한다는 의미를 나타냄.
- 일반적인 파이프라인 스타일:
- _는 로대시(Lodash)나 언더스코어(Underscore.js) 라이브러리에서 함수형 프로그래밍 스타일을 지원하는 유틸리티 함수들의 네임스페이스로 사용된다. 예를 들어, _.map이나 _.filter 같은 함수 호출에서 _는 해당 라이브러리의 네임스페이스를 나타냄
- 임시 변수:
- 반복문이나 람다 표현식 등에서 사용되지 않는 변수에 _를 사용한다. 이는 해당 변수가 사용되지 않을 것임을 명확히 하는 데 도움이 됨.
여기서 _siftUp과 _siftDown 메서드는 MinHeap 클래스의 내부 메서드로, 외부에서 직접 호출하지 않도록 하기 위한 암묵적인 표시로 _를 사용한 예시이다.
function이 아닌 클래스로 짜는 이유
- 구조화:
- MinHeap 클래스 내에 힙과 관련된 모든 메서드(push, pop, _siftUp, _siftDown, _greater, _swap)가 포함되어 있어 힙의 동작을 명확하게 이해하고 유지할 수 있다. 이는 코드의 모듈화를 돕고, 객체 지향 프로그래밍의 장점을 활용할 수 있게 한다.
- 함수 기반 접근법은 더 간단하고 직접적일 수 있지만, 관련된 데이터와 동작을 명시적으로 묶지 않습니다. 이는 코드의 가독성이나 유지보수성에서 차이를 만들 수 있다.
- 재사용성:
- MinHeap 클래스를 여러 알고리즘이나 프로그램에서 인스턴스화하여 사용할 수 있다. 예를 들어, 여러 종류의 우선순위 큐가 필요한 다양한 문제에서 재사용할 수 있다.
- 함수 기반 접근법에서도 함수를 재사용할 수 있지만, 여러 개의 힙을 동시에 사용해야 하는 경우 클래스를 사용하는 것이 더 간단하다.
- 유지보수성:
- 힙의 동작을 수정해야 할 때, MinHeap 클래스 내의 메서드만 수정하면 됩니다. 다른 곳에서 이 클래스를 사용하는 코드에는 영향을 미치지 않는다.
- 함수 기반 접근법에서는 관련된 함수들이 전역적으로 존재하기 때문에, 유지보수 시 더 많은 주의가 필요할 수 있다.
- 클래스의 메서드들은 클래스의 인스턴스 내에 존재하므로, 전역적으로 존재하지 않습니다. 이는 클래스의 주요 장점 중 하나로, 네임스페이스 충돌을 피하고 코드의 모듈화를 촉진한다.
- 상속과 다형성:
- 다른 종류의 힙 (예: 최대 힙)을 만들고 싶다면, MinHeap 클래스를 상속받아 필요한 메서드만 재정의할 수 있다.
- 함수 기반 접근법에서는 이러한 상속 및 다형성을 직접적으로 제공하지 않기 때문에, 동일한 기능을 구현하기 위해 더 많은 코드가 필요할 수 있다.
결론적으로, 함수로도 구현할 수 있지만, 클래스는 코드의 구조화, 재사용성, 유지보수성 측면에서 더 많은 이점을 제공한다.
'알고리즘' 카테고리의 다른 글
[알고리즘]프로그래머스 - N으로 표현 <동적계획법(DP)> (0) | 2024.03.04 |
---|---|
[알고리즘] 백준 13904 과제 node.js (Greedy) (0) | 2024.02.23 |
[알고리즘] 탐욕법(Greedy) (0) | 2024.02.06 |
[알고리즘] 완전탐색 예제 # 1 단순 브루트포스 (0) | 2024.02.05 |
[알고리즘] 완전 탐색 (0) | 2024.02.02 |