[프로그래머스/JS] Lv2. 더 맵게 (힙 자료구조, 우선순위 큐 구현)
문제
https://school.programmers.co.kr/learn/courses/30/lessons/42626
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
풀이
우선 순위 큐를 구현해야하는 문제이다. 자바에서는 라이브러리를 불러오면 쉽게 해결되지만, 자바스크립트에서는 직접 구현을 해야한다.
우선 순위 큐를 어떻게 구현할 수 있을까? 우선 순위 큐는 힙 자료 구조를 알면 쉽게 접근해볼 수 있다.
힙은 완전 이진 트리의 일종이다. 특징은 부모 노도의 키 값이 자식 노드의 키 값보다 항상 큰 이진 트리이다.
여기서 힙의 종류는 두 가지가 있다.
어려운 것은 아니고, 값이 큰 게 우선인가 작은 것이 우선인가로 나누어볼 수 있는 것이다.
그럼 이 힙을 어떻게 구현해야할까? 답은 배열로 구현할 수 있다.
힙의 루트부터 아래로 인덱스를 매겨보면, 왼쪽 자식의 인덱스는 부모의 인덱스의 *2이고 오른쪽 자식 인덱스는 부모 인덱스 *2 +1 이라는 것을 확인할 수 있다. 반대로 부모의 인덱스는 자식의 인덱스/2 한 값이다. 이것을 배열에 넣으면 힙을 간접적으로 표현할 수 있는 것이다.
힙에 대해서는 정리가 된 것 같다. 이제 그럼 우선 순위를 어떻게 나타낼 수 있을까? 새로운 요소를 삽입하고 삭제할 때, 그에 알맞게 정렬해주면 우선 순위를 유지할 수가 있다.
삽입하는 경우를 그림으로 쉽게 살펴보자.
삽입한 요소를 부모와 비교하며, 조건에 맞지 않을 때까지, 교환하는 과정을 거치는 것을 알 수 있다.
이것을 자바 스크립트 코드로 나타낸 것은 아래와 같다. 참고로 최소 힙을 구현한 것이다.
주석을 통해 코드를 설명했다.
class MinHeap{
constructor(){
this.heap = []; //배열을 선언한다.
}
push(item){ //삽입
this.heap.push(item); //배열의 가장 마지막에 값을 삽입한다.
let index = this.heap.length-1;
//삽입한 값이 루트가 되거나, 부모값보다 작은 경우가 아닐 때까지 계속해서 스왑한다.
while(index > 0
&& this.heap[index] < this.heap[Math.floor((index-1)/2)])
{
const temp = this.heap[index];
this.heap[index] = this.heap[Math.floor((index-1)/2)];
this.heap[Math.floor((index-1)/2)] = temp;
index = Math.floor((index-1)/2);
}
}
pop(){ //최상단의 루트 값을 빼낸다. 빼내고 나서 재정렬을 해주어야한다.
if(this.heap.length===0) return null;
if(this.heap.length===1) return this.heap.pop(); //만약 하나밖에 없다면 오버헤드 줄이기
const minValue = this.heap[0]; //반환해야할 값
this.heap[0] = this.heap.pop();
let index = 0;
while(index*2+1 < this.heap.length){ //자식 인덱스가 전체 배열 길이보다 작다면 반복
//교환할 자식 인덱스를 선택한다.
let minChildIndex = index * 2 + 2 < this.heap.length // 오른쪽 자식이 힙의 길이보다 작은지를 체크한다.
&& this.heap[index * 2 + 2] < this.heap[index * 2 + 1] // 오른쪽자식 노드값이 왼쪽자식보다 작은지 확인한다.
? index * 2 + 2 조건에 부합하면 오른쪽
: index * 2 + 1; 아니라면 왼쪽을 선택한다.
if(this.heap[index] < this.heap[minChildIndex]){ //만약 자식이 인덱스보다 크다면 거기서 멈춘다.
break;
}
//스왑
const temp = this.heap[index];
this.heap[index] = this.heap[minChildIndex];
this.heap[minChildIndex] = temp;
index = minChildIndex;
}
return minValue;
}
}
이를 이용해 문제를 해결한 것은 아래와 같다.
소스 코드
function solution(scoville, K) {
var answer = 0;
let heap = new MinHeap();
for(let i =0;i<scoville.length;i++){
heap.push(scoville[i]);
}
let count = 0;
while(heap.peek()<K){
let food1 = heap.pop();
let food2 = heap.pop();
let newFood = food1+food2*2;
heap.push(newFood);
count++;
}
answer = heap.peek()>=K ? count: -1;
return answer;
}
class MinHeap{
constructor(){
this.heap = [];
}
size(){
return this.heap.length;
}
push(item){
this.heap.push(item);
let index = this.heap.length-1;
while(index > 0
&& this.heap[index] < this.heap[Math.floor((index-1)/2)])
{
const temp = this.heap[index];
this.heap[index] = this.heap[Math.floor((index-1)/2)];
this.heap[Math.floor((index-1)/2)] = temp;
index = Math.floor((index-1)/2);
}
}
pop(){
if(this.heap.length===0) return null;
if(this.heap.length===1) return this.heap.pop();
const minValue = this.heap[0];
this.heap[0] = this.heap.pop();
let index = 0;
while(index*2+1 < this.heap.length){
let minChildIndex = index * 2 + 2<this.heap.length
&& this.heap[index*2+2] < this.heap[index*2+1]?index*2+2:index*2+1;
if(this.heap[index] < this.heap[minChildIndex]){
break;
}
const temp = this.heap[index];
this.heap[index] = this.heap[minChildIndex];
this.heap[minChildIndex] = temp;
index = minChildIndex;
}
return minValue;
}
peek(){
return this.heap[0];
}
}
참고자료
https://velog.io/@eldoradodo/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-JavaScript-%EB%8D%94-%EB%A7%B5%EA%B2%8C
https://velog.io/@eldoradodo/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-JavaScript-%EB%8D%94-%EB%A7%B5%EA%B2%8C
https://mingmeng030.tistory.com/293