프로그래머스 고득점 Kit - [더 맵게] 해설

고득점 Kit - Heap(힙)
Lv.2 - 더 맵게 해설 코드 공유합니다

많은 초보자 분들이 코딩을 하실 때 흔히 하는 실수가, 배열(array)로 제공된 자료구조를 무조건 배열로만 풀려고 한다는 것입니다.

이 문제를 보시면 가장 작은 두 요소를 섞어서 새로운 하나의 요소를 추가하는 매우 단순한 알고리즘으로 구성되어있습니다. 이 알고리즘을 짜는 것은 아무리 초보자라도 누구나 다 할 수 있을 겁니다.

하지만 문제는 그 다음부터입니다. 분명 완벽하게 작동하는 알고리즘을 만들었는데도 불구하고 실행시키면 바로 효율성 테스트를 광탈하고 절망하는 여러분의 모습을 보실 수 있을 것입니다.

그렇다면 왜 이렇게 타임아웃이 나고 시간효율이 떨어지는 것일까요? 초보자의 관점에서 설명을 드리자면, 먼저 배열의 고질적인 문제점을 알아야합니다.

배열이 가진 고질적인 문제

배열은 인덱스 0번을 기준으로 차곡차곡 데이터를 쌓아나갑니다. 그래서 인덱스 0번에 새로운 요소를 추가하면 다른 모든 요소들이 뒤로 한 칸씩 옮겨져야하는 매우 말도안되게 비효율적인 추가동작이 필요하게 됩니다.
( 아마 시간복잡도는 O(n)이 되겠죠? )

이러한 비효율적인 동작은 데이터량이 커졌을 때 어마무시한 비효율성을 초래합니다. 그리고 이는 곧 '시간 초과'라는 결과를 가져오게 되는 것이죠.

그렇다면 과연 어떻게 해야 이 문제를 해결할 수 있을까요?

스택(stack)과 큐(queue)

아무리 초보자라도 스택, 큐 등이 무엇인지는 들어보셨을 것이라고 생각됩니다. 스택은 LIFO(후입선출), 큐는 FIFO(선입선출). 배열은 이 중 스택에 해당합니다.

그리고 제가 앞서 앞에서 언급한 배열의 고질적인 문제를 해결하려면 반드시 큐를 사용해야 한다는 것도 아마 윗 글을 읽으면서 생각하셨을 것입니다.

그렇다면 정말 큐만 사용하면 모든 문제가 해결될까요?

우선순위 큐(priority queue)의 등장

이 문제를 보시면 메인 알고리즘은 두 최솟값을 pop한 후 그 두 값을 계산하여 새로운 값을 생성하고, 그 새로운 값을 배열에 입력한 후 다시 sort하는 과정의 반복이라고 할 수 있습니다.

이 과정을 그대로 가지고 있는 자료구조가 바로 우선순위 큐(priority queue)입니다. 우선순위 큐는 말그대로 일차원 큐를 우선순위를 가지고 정렬해 두는 자료구조를 의미합니다.

하지만 이보다 훨씬 더 좋은 자료구조가 있습니다. 그것이 바로 오늘의 주제 힙(Heap)입니다.

오늘의 주제 : 힙(Heap)

힙 트리 = 우선순위 큐

라고 생각하시는 분들이 계실 겁니다. 저도 그랬었구요. 하지만 조금 다릅니다. 힙트리는 우선순위 큐를 이진트리 구조로 표현한 형식으로 정렬의 시간복잡도가 무려 O(log n)인 엄청난 효율성을 가진 자료구조입니다.

이 힙(Heap)을 알고만 있었다면 오늘 문제 매우 간단하게 해결이 가능합니다.

힙(Heap) 구현하기

Python과 같은 언어에서는 힙을 외부모듈을 Import 하는 과정으로 매우 간단하게 해결할 수 있습니다.

하지만 그렇게 쉽게 누군가가 만들어놓은 모듈을 사용하는 습관을 가지게되면, 그 자료구조를 완벽하게 이해할 수 없고, 또 나중에 외부모듈을 사용할 수 없다는 조건이 걸리기라도하면 아무것도 할 수 없겠죠.

그래서 저는 배움의 차원에서라도 힙트리를 구현해보는 것을 추천드립니다.

다음은 MinHeap을 구현한 Class 입니다.

주석을 자세히 달아두었으니 읽어보면서 따라해보시기 바랍니다.

class MinHeap {
    //생성자 함수
    constructor() {
        this.heap = [];
    }
    
    //index를 가져오는 함수
    getParentIdx(childIdx) {
        return Math.floor((childIdx - 1) / 2);
    }
    getLeftChildIdx(parentIdx) {
        return (parentIdx *  2) + 1;
    }
    getRightChildIdx(parentIdx) {
        return (parentIdx * 2) + 2;
    }
    
    //heap tree의 노드개수를 세어주는 함수
    size() {
        return this.heap.length;
    }
    
    //두 값을 swap해준다.
    swap(Idx_1, Idx_2) {
        [this.heap[Idx_1], this.heap[Idx_2]] = [this.heap[Idx_2], this.heap[Idx_1]];
        
        return this.heap;
    }
    
    //새로운 노드를 heap tree의 마지막 노드에 push해주는 함수
    push(value) {
        this.heap.push(value);
        this.bubbleUp();
        
        return this.heap;
    }
    //최상단 head node를 pop해주는 함수
    pop() {
        if(this.size() == 1) {
            return this.heap.pop();
        }
        if(this.size() == 0) {
            return null;
        }
        const value = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.bubbleDown();
        return value;
    }
    
    //맨 마지막 노드에서 출발해서 최상단 노드까지 올라가면서 bubble up 한다.
    bubbleUp() {
        let child_Idx = this.size() - 1;
        let parent_Idx = this.getParentIdx(child_Idx);
        
        while (this.heap[child_Idx] < this.heap[parent_Idx]) {
            this.swap(child_Idx, parent_Idx);
            child_Idx = parent_Idx;
            parent_Idx = this.getParentIdx(child_Idx);
        }
    }
    
    //최상단 노드에서 마지막노드까지 내려가면서 bubble down 한다.
    bubbleDown() {
        let parent_Idx = 0;
        let left_Idx = this.getLeftChildIdx(parent_Idx);
        let right_Idx = this.getRightChildIdx(parent_Idx);

        while((left_Idx <= this.size() - 1 && this.heap[left_Idx] < this.heap[parent_Idx]) || (right_Idx <= this.size() - 1 && this.heap[right_Idx] < this.heap[parent_Idx])) {
            //오른쪽이 왼쪽보다 작고 오른쪽 노드가 존재한다면
            if(this.heap[right_Idx] < this.heap[left_Idx] && right_Idx <= this.size() - 1){
                //오른쪽과 부모노드를 swap 한다.
                this.swap(right_Idx, parent_Idx);
                parent_Idx = right_Idx;
                right_Idx = this.getRightChildIdx(parent_Idx);
                left_Idx = this.getLeftChildIdx(parent_Idx);
            } else {
                //왼쪽과 부모노드를 swap 한다.
                this.swap(left_Idx, parent_Idx);
                parent_Idx = left_Idx;
                right_Idx = this.getRightChildIdx(parent_Idx);
                left_Idx = this.getLeftChildIdx(parent_Idx);
            }
        }
    }
}

메인 함수 코드

위와같이 클래스를 작성하셨다면 그 다음은 식은죽 먹기죠.
그냥 클래스의 메소드를 사용해서 가볍게 풀어주시면 되겠습니다.

주석을 자세히 달아두었으니 읽어보시고 모르는 부분은 댓글로 남겨주시면 답변해드리겠습니다.

function solution(scoville, K) {
    let answer = 0;
    
    //우선순위큐(heap) 생성
    const heap = new MinHeap();
    
    //scoville에 있는 각각의 요소를 forEach를 이용하여 sorting 한다.
    scoville.forEach(value => heap.push(value));
    
    while(heap.heap[0] < K && heap.size() > 1) {
        //첫번째 pop의 값과 두번째 pop의 2배의 합을 newfood 변수에 저장
        const first_pop = heap.pop();
        const second_pop = heap.pop();
        const newfood = first_pop + (second_pop * 2);

        //newfood를 다시 heap 트리에 삽입
        heap.push(newfood);
        //1번 루프를 돌 때마다 answer에 1 추가
        answer++;
    }

    if(heap.heap[0] >= K) {
        return answer;
    } else {
        return -1;
    }
}

도움이 되셨다면 댓글 부탁드립니다.
그럼 다음에 더 좋은 해설로 돌아오겠습니다.