[JS] 코딩테스트 고득점 Kit - 힙 한번에 정리하기

힙도 level 2 이하가 한문제라 이문제만 올려놓습니다! 

더 맵게 level 2

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

    getPIdx(idx) {
        return Math.floor((idx - 1) / 2);
    }

    getLIdx(idx) {
        return idx * 2 + 1;
    }

    getRIdx(idx) {
        return idx * 2 + 2;
    }

    swap(idx1, idx2) {
        [this.heap[idx1], this.heap[idx2]] = [this.heap[idx2], this.heap[idx1]];
    }

    push(value) {
        this.heap.push(value);

        let curIdx = this.heap.length - 1;
        let pIdx = this.getPIdx(curIdx);

        while (curIdx > 0 && this.heap[curIdx] < this.heap[pIdx]) {
            this.swap(curIdx, pIdx);
            curIdx = pIdx;
            pIdx = this.getPIdx(curIdx);
        }
    }

    pop() {
        if (this.heap.length === 0) return null;
        if (this.heap.length === 1) return this.heap.pop();

        const root = this.heap[0];
        this.heap[0] = this.heap.pop();

        let curIdx = 0;

        while (true) {
            let lIdx = this.getLIdx(curIdx);
            let rIdx = this.getRIdx(curIdx);
            let smallestIdx = curIdx;

            if (lIdx < this.heap.length && this.heap[lIdx] < this.heap[smallestIdx]) {
                smallestIdx = lIdx;
            }

            if (rIdx < this.heap.length && this.heap[rIdx] < this.heap[smallestIdx]) {
                smallestIdx = rIdx;
            }

            if (smallestIdx === curIdx) break;

            this.swap(curIdx, smallestIdx);
            curIdx = smallestIdx;
        }

        return root;
    }

    isEmpty() {
        return this.heap.length === 0;
    }

    peek() {
        return this.heap[0] || null;
    }
}


function solution(scoville, K) {
    // 먼저 MinHeap 클래스의 인스턴스 minHeap을 생성합니다.
    const minHeap = new MinHeap();

    // for 반복문을 사용하여 scoville 배열의 모든 요소를 minHeap에 삽입합니다.
    for (let i = 0; i < scoville.length; i++) {
        minHeap.push(scoville[i]);
    }

    // count 변수를 초기화하여 섞은 횟수를 저장합니다.
    let count = 0;

    // while 반복문을 사용하여 minHeap의 루트 노드(가장 작은 스코빌 지수)가 K 미만인 동안 반복합니다.
    while (minHeap.heap[0] < K) {

        // 만약 minHeap에 요소가 1개밖에 없다?
        // 그러면 합할 개수 부족으로 모든 음식을 K 이상으로 만들 수 없으므로 -1을 반환합니다.
        if (minHeap.heap.length === 1) return -1;

        // minHeap에서 가장 작은 스코빌 지수 first와 두 번째로 작은 스코빌 지수 second를 꺼냅니다.
        const first = minHeap.pop();
        const second = minHeap.pop();

        // 섞은 음식의 스코빌 지수 mixed를 계산합니다.
        const mixed = first + second * 2;

        // mixed를 다시 minHeap에 삽입합니다.
        minHeap.push(mixed);

        // 섞은 횟수 count를 1 증가시킵니다.
        count++;
    }

    // while 반복문이 종료되면 모든 음식의 스코빌 지수가 K 이상이 된 것입니다.
    // 그러므로 섞은 횟수 count를 반환합니다.
    return count;
}

 

MinHeap 클래스

최소 힙은 가장 작은 값이 루트에 위치하는 트리 구조입니다. 이 클래스를 통해 데이터를 정렬하며, 값들을 효율적으로 삽입하고 삭제할 수 있습니다.

1. 생성자 (constructor)

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

heap 배열을 초기화합니다. 여기에 최소 힙 구조로 값을 저장합니다.

2. 부모, 왼쪽, 오른쪽 자식 인덱스 구하기

getPIdx(idx) { return Math.floor((idx - 1) / 2); }
getLIdx(idx) { return idx * 2 + 1; }
getRIdx(idx) { return idx * 2 + 2; }

• getPIdx: 부모 인덱스를 구하는 함수입니다.
• getLIdx & getRIdx: 각각 왼쪽, 오른쪽 자식 인덱스를 계산하는 함수입니다.

3. 값 교환 (swap)

   swap(idx1, idx2) {
   [this.heap[idx1], this.heap[idx2]] = [this.heap[idx2], this.heap[idx1]];
   }

• 힙의 두 인덱스 값을 서로 교환합니다.

4. 값 추가 (push)

push(value) {
    this.heap.push(value);
    let curIdx = this.heap.length - 1;
    let pIdx = this.getPIdx(curIdx);
    
    while (curIdx > 0 && this.heap[curIdx] < this.heap[pIdx]) {
        this.swap(curIdx, pIdx);
        curIdx = pIdx;
        pIdx = this.getPIdx(curIdx);
    }
}

• 새로운 값을 힙에 추가한 후, 부모와 비교하여 작으면 부모와 교환하면서 위로 올라갑니다. 최종적으로 힙의 규칙을 유지합니다.

5. 값 제거 (pop)

pop() {
    if (this.heap.length === 0) return null;
    if (this.heap.length === 1) return this.heap.pop();
    
    const root = this.heap[0];
    this.heap[0] = this.heap.pop();
    
    let curIdx = 0;
    
    while (true) {
        let lIdx = this.getLIdx(curIdx);
        let rIdx = this.getRIdx(curIdx);
        let smallestIdx = curIdx;
        
        if (lIdx < this.heap.length && this.heap[lIdx] < this.heap[smallestIdx]) {
            smallestIdx = lIdx;
        }
        
        if (rIdx < this.heap.length && this.heap[rIdx] < this.heap[smallestIdx]) {
            smallestIdx = rIdx;
        }
        
        if (smallestIdx === curIdx) break;
        
        this.swap(curIdx, smallestIdx);
        curIdx = smallestIdx;
    }
    
    return root;
}

 

 

• 가장 작은값(루트값)을 제거합니다
  • 마지막 값을 루트로 옮기고, 자식들과 비교하면서 내려가 힙 규칙을 다시 맞춥니다.
• 기타함수
  • isEmpty(): 힙이 비어있는지 확인하는 함수입니다
  • peek(): 루트 값을 반환하지만 힙을 수정하지 않습니다.

 

Solution 함수

이 함수는 문제를 해결하는 핵심 로직으로, 힙을 사용해 스코빌 지수가 K 이상이 되도록 음식을 섞는 과정을 구현합니다.

1. 초기화

const minHeap = new MinHeap();
for (let i = 0; i < scoville.length; i++) {
    minHeap.push(scoville[i]);
}

• 주어진 scoville 배열의 값을 모두 minHeap에 추가해 최소 힙을 구성합니다.

 

2. 섞는 과정

let count = 0;
while (minHeap.heap[0] < K) {
    if (minHeap.heap.length === 1) return -1;
    
    const first = minHeap.pop();
    const second = minHeap.pop();
    
    const mixed = first + second * 2;
    minHeap.push(mixed);
    count++;
}

• 힙에서 가장 작은 값이 K 이상이 될 때까지 음식을 섞습니다.
• 가장 작은 값 두 개를 꺼내 새로운 스코빌 지수를 만들고 다시 힙에 넣습니다.
• 섞은 횟수는 count에 기록됩니다.

3. 결과 반환
   return count;
   • 모든 음식의 스코빌 지수가 K 이상이 되면 섞은 횟수를 반환합니다.