꒰ྀི 01. 프로그래머스:: 더 맵게

문제 요약

 

- Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들 예정이다.

- 가장 맵지 않은 두 개의 음식을 섞어 새로운 음식을 만든다.

 

과정을 반복해 모든 음식의 스코빌 지수가 K 이상이 되도록 만든다.

최소 몇 번을 섞어야하는가?

 

자료구조 선택

 

최소값 또는 최대값을 찾아내야 하는 문제다.

가장 맵지 않은 두 개의 음식을 빠르게 찾아내야 하기 때문에

가장 적합한 자료구조로 최소 힙을 선택하였다.

 

최소 힙은 루트 노드가 항상 최솟값을 가진다.

 

문제 해결 과정

 

1. 스코빌 지수 배열을 최소 힙으로 변환한다.

    이 과정 이후, 배열에서 가장 작은 값을 빠르게 찾을 수 있다.

2. 반복문

  - 힙에서 가장 맵지 않은 음식을 꺼냄

  - 두 번째로 맵지 않은 음식을 꺼냄

  - 새로운 스코빌 지수 계산

  - 새로운 음식을 힙에 넣음

  - 모든 음식이 스코빌 지수 K가 넘을 때까지 반복

3. 힙의 최솟값이 K 이상이면 종료

 

function solution(scoville, K) {
    scoville.sort((a, b) => a - b);
    
    let mixCount = 0;

    while (scoville[0] < K) {
        if (scoville.length < 2) {
            return -1; 
        }

        const first = scoville.shift();
        const second = scoville.shift();
        const newScoville = first + (second * 2);
        
        scoville.push(newScoville);
        scoville.sort((a, b) => a - b); 
        
        mixCount += 1;
    }

    return mixCount;
}

 

힙 (최소 힙, 최대 힙)

 

문제는 이 코드가 모두 효율성 테스트를 통과하지 못했다는 점이다.

 

뭐가 문제일까?

2단계 문제의 장벽이 너무 높다.

사용자의 코드에서 주의할 점은 sort 함수의 사용입니다.
sort 함수는 효율성이 낮아서, 음식을 매번 섞을 때마다 배열 전체를 정렬하면 시간 복잡도가 높아집니다. 대신 이 문제는 '힙(Heap)' 자료구조를 사용하면 더 효율적으로 해결할 수 있습니다. JavaScript에서는 기본적으로 힙 자료구조를 제공하지 않지만, 우선순위 큐를 직접 구현하거나 외부 라이브러리를 활용하여 힙과 유사한 기능을 구현할 수 있습니다. 문제의 키 포인트는 항상 스코빌 지수가 가장 낮은 두 개의 음식을 찾아야 한다는 것인데, 이를 힙을 활용해서 구현하면 매번 전체를 정렬할 필요 없이 효율적으로 두 최소값을 찾을 수 있습니다. 따라서 힙을 사용해 해결 방법을 고민해 보세요.

 

이런 대답을 얻었기 때문에,

그냥 코드의 수가 증가하더라도 직접 우선순위 큐를 구현해보았다.

 

[JS] 우선순위 큐 (Priority Queue)

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

    getParentIndex(index) {
        return Math.floor((index - 1) / 2);
    }

    getLeftChildIndex(index) {
        return index * 2 + 1;
    }

    getRightChildIndex(index) {
        return index * 2 + 2;
    }

    swap(index1, index2) {
        [this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]];
    }

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

    heapifyUp() {
        let index = this.heap.length - 1;
        while (this.getParentIndex(index) >= 0 && this.heap[this.getParentIndex(index)] > this.heap[index]) {
            this.swap(this.getParentIndex(index), index);
            index = this.getParentIndex(index);
        }
    }

    pop() {
        if (this.heap.length === 1) return this.heap.pop();
        const root = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.heapifyDown(0);
        return root;
    }

    heapifyDown(index) {
        let smallest = index;
        const leftChild = this.getLeftChildIndex(index);
        const rightChild = this.getRightChildIndex(index);

        if (leftChild < this.heap.length && this.heap[leftChild] < this.heap[smallest]) {
            smallest = leftChild;
        }

        if (rightChild < this.heap.length && this.heap[rightChild] < this.heap[smallest]) {
            smallest = rightChild;
        }

        if (smallest !== index) {
            this.swap(index, smallest);
            this.heapifyDown(smallest);
        }
    }

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

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

function solution(scoville, K) {
    const minHeap = new MinHeap();

    for (let num of scoville) {
        minHeap.push(num);
    }

    let mixCount = 0;

    while (minHeap.peek() < K) {
        if (minHeap.size() < 2) {
            return -1; 
        }

        const first = minHeap.pop();
        const second = minHeap.pop();
        const newScoville = first + (second * 2);
        minHeap.push(newScoville);
        mixCount += 1;
    }

    return mixCount;
}

 

통과할 수 있었다...ㅎ

자바스크립트는 따로 제공되는 힙 클래스가 없기 때문에

직접 구현하거나 라이브러리를 사용해야한다.

 

시험 환경이 어떠할지 알 수 없기 때문에, 따로 힙 클래스를 구현해보았다.