코딩테스트 최소 힙(MinHeap)을 활용한 "더 맵게" 문제 해결법

코딩테스트 최소 힙(MinHeap)을 활용한 "더 맵게" 문제 해결법

 

 

프로그래밍 문제 해결에 있어 데이터 구조의 선택은 효율성을 결정짓는 중요한 요소입니다. "더 맵게" 문제는 스코빌 지수를 조작하여 문제의 요구사항을 충족시키는 최소 횟수를 찾는 과정에서, 시간 복잡도를 줄이기 위한 적절한 데이터 구조의 필요성을 강조합니다. 이 글에서는 초기 접근 방법의 문제점과, 최소 힙(MinHeap) 구조를 이용한 해결 방안을 소개하고자 합니다.

 

 

코딩테스트 힙 문제

 

▼ 더 맵게 문제 ▼

프로그래머스

 

"더 맵게" 문제는 프로그래밍 테스트에서 자주 등장하는 힙(Heap)을 활용한 문제입니다. 주어진 스코빌 지수를 K 이상으로 만들기 위해 가장 맵지 않은 두 음식을 섞는 과정을 최소화하는 것이 목표입니다.

 

 

문제점 인식

function solution(scoville, K) {
    var answer = 0;

    let arr = [...scoville];

    // console.log(arr);
    // console.log(arr[0]);
    // console.log(arr[1]);

    while(true){
        arr = arr.map(x => Number(x)).sort((a, b) => a - b);;

        // console.log("arr:",arr);

        let flag = true;

        arr.forEach((x,i)=>{

            if(x<K) flag = false;

        });

        if(flag) return answer;

        // 섞을 수 있는 음식이 없는 경우
        if(arr.length < 2) return -1;

        arr.push(Number(arr[0])+(Number(arr[1])*2));
        arr.shift();
        arr.shift();

        answer+=1;

    }
}

 

처음 작성한 코드는 배열을 이용하여 스코빌 지수가 낮은 음식 두 개를 섞는 과정을 반복합니다. 이때, sort 메소드를 사용하여 매번 배열을 정렬하고, 가장 낮은 두 스코빌 지수를 추출해 새로운 음식을 만드는 방식을 취했습니다. 하지만, 이 방법은 배열의 길이에 따라 sort 함수의 시간 복잡도가 증가하며, 특히 배열의 길이가 클 때 효율성 문제로 이어집니다. 즉, 시간 초과 오류가 발생하는 원인입니다.

 

 

최소 힙(MinHeap)을 이용한 해결 방안

최소 힙은 부모 노드가 자식 노드보다 항상 작거나 같은 완전 이진 트리 구조로, 루트 노드에 항상 가장 작은 값이 위치합니다. 이러한 특성을 활용하면, 매번 정렬할 필요 없이 가장 낮은 스코빌 지수를 빠르게 추출할 수 있습니다.

 

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

    insert(value) {
        this.heap.push(value);
        this.bubbleUp();
    }

    bubbleUp() {
        let index = this.heap.length - 1;
        const lastInsertedNode = this.heap[index];

        while (index > 0) {
            const parentIndex = Math.floor((index - 1) / 2);
            if (this.heap[parentIndex] > lastInsertedNode) {
                this.heap[index] = this.heap[parentIndex];
                index = parentIndex;
            } else {
                break;
            }
        }

        this.heap[index] = lastInsertedNode;
    }

    extractMin() {
        const min = this.heap[0];
        if (this.heap.length === 1) {
            this.heap.pop();
        } else {
            this.heap[0] = this.heap.pop();
            this.sinkDown(0);
        }

        return min;
    }

    sinkDown(index) {
        let smallest = index;
        const leftChildIndex = 2 * index + 1;
        const rightChildIndex = 2 * index + 2;
        const length = this.heap.length;

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

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

        if (smallest !== index) {
            [this.heap[smallest], this.heap[index]] = [this.heap[index], this.heap[smallest]];
            this.sinkDown(smallest);
        }
    }
}

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

    scoville.forEach(scoville => minHeap.insert(scoville));

    while (minHeap.heap[0] < K) {
        if (minHeap.heap.length < 2) return -1;
        const firstMin = minHeap.extractMin();
        const secondMin = minHeap.extractMin();

        const mixedScoville = firstMin + secondMin * 2;
        minHeap.insert(mixedScoville);
        answer++;
    }

    return answer;
}

 

위 MinHeap 클래스는 스코빌 지수 배열을 최소 힙으로 관리하며, 가장 낮은 두 값을 추출하여 새 스코빌 지수를 계산하고 다시 힙에 삽입하는 과정을 반복합니다. 이를 통해, 각 단계에서 배열 전체를 정렬하는 것보다 훨씬 빠르게 원하는 결과를 도출할 수 있습니다.

 

---

 

끝으로

"더 맵게" 문제 해결을 위한 최소 힙(MinHeap)의 도입은 시간 복잡도 문제를 해결하는 효과적인 방법입니다. 배열을 사용한 초기 접근 방법에서 발생한 시간 초과 문제를 해결하며, 더 효율적인 코드 실행을 가능하게 합니다. 최소 힙을 사용함으로써, 우리는 알고리즘의 실행 시간을 대폭 줄일 수 있었으며, 이는 프로그래밍 문제 해결에 있어 데이터 구조의 중요성을 다시 한번 강조합니다.

 

이번 경험을 통해, 단순한 문제 해결 방법에서 한 걸음 더 나아가, 문제를 효율적으로 해결하기 위한 데이터 구조의 선택이 얼마나 중요한지를 배울 수 있었습니다. 특히, 복잡한 문제를 해결하거나, 대규모 데이터를 다룰 때, 적절한 데이터 구조를 선택하는 것이 결과의 질과 실행 속도에 결정적인 영향을 미친다는 것을 확인할 수 있었습니다.

 

 

최소 힙 구조의 도입은 "더 맵게" 문제뿐만 아니라 다양한 알고리즘 문제 해결에도 응용될 수 있으며, 이러한 구조를 이해하고 활용하는 능력은 알고리즘 문제 해결 능력을 한층 더 향상시킬 수 있습니다. 따라서, 알고리즘과 자료 구조에 대한 깊은 이해를 바탕으로, 보다 나은 솔루션을 설계하는 능력을 개발하는 것이 중요합니다.

 

이 글이 프로그래밍 문제 해결에 있어서 효율적인 데이터 구조 선택의 중요성을 이해하는 데 도움이 되었기를 바랍니다. 여러분의 알고리즘 문제 해결 과정에 최소 힙과 같은 데이터 구조가 실질적인 도움이 되길 바랍니다.

 

▼ 30초 더 투자하면 얻게되는 정보 ▼

 

코딩테스트 스택(stack) 문제 - 같은 숫자는 싫어 해결 과정

 

1974. Minimum Time to Type Word Using Special Typewriter