[JS] 더 맵게

 

 

난이도: Lv. 2

문제: https://school.programmers.co.kr/learn/courses/30/lessons/42626

프로그래머스

 

 

알고리즘

힙 구현

insert 구현

• 배열의 맨 뒤에 삽입할 데이터를 push()하고, 업 버블링을 한다. 삽인한 데이터가 부모 노드의 값보다 클 때까지 반복한다.

delete 구현

• 배열의 맨 앞에 있는 값을 따로 저장하고 delete 함수의 마지막에서 반환한다.
• 배열의 맨 앞 값을 저장한 후 배열의 맨 뒷 값을 pop()하여 배열의 맨 앞 원소에 덮어씌우고, 다운 버블링을 한다. 해당 원소가 자식 노드의 값보다 크면 자식 노드와 교체해야 하며, 해당 원소가 두 자식 모두보다 크면 두 자식 중 더 작은 자식과 바꿔야 한다. 더 이상 자식 노드가 존재하지 않거나 두 자식 모두보다 해당 원소가 작다면 종료한다.

힙을 이용한 문제 풀이

위에서 구현한 힙에 주어진 배열 scoville의 원소를 하나씩 insert() 한다.

힙의 맨 앞 원소가 가장 작은 원소이다. 이 원소가 K 이상이면 음식을 섞지 않아도 되므로 0을 반환한다.

힙에서 가장 작은 스코빌 지수가 K 이상이거나 힙의 길이가 1이 될 때까지 음식을 섞는다. while 문을 벗어난 경우는 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우이므로 -1을 반환한다.

 

 

코드

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

    const Heap = {
        arr: [],
        insert: function (data) {
            this.arr.push(data);
            let currentIdx = this.arr.length - 1;
            let parentIdx = Math.floor((currentIdx - 1) / 2);
            while (currentIdx !== 0 && this.arr[parentIdx] > data) {
                [this.arr[parentIdx], this.arr[currentIdx]] = [this.arr[currentIdx], this.arr[parentIdx]]; // switch
                currentIdx = parentIdx;
                parentIdx = Math.floor((currentIdx - 1) / 2);
            }
        },
        delete: function () {
            const root = this.arr[0];
            if (this.arr.length === 1) { this.arr.pop(); return root; }
            this.arr[0] = this.arr.pop();

            let currentIdx = 0;
            while (true) {
                let leftChildIdx = 2 * currentIdx + 1;
                let rightChildIdx = 2 * currentIdx + 2;

                if (leftChildIdx >= this.arr.length && rightChildIdx >= this.arr.length) { break; }

                if (this.arr[currentIdx] > this.arr[leftChildIdx] && this.arr[currentIdx] > this.arr[rightChildIdx]) {
                    const minIdx = this.arr[leftChildIdx] > this.arr[rightChildIdx] ? rightChildIdx : leftChildIdx;
                    [this.arr[currentIdx], this.arr[minIdx]] = [this.arr[minIdx], this.arr[currentIdx]];
                    currentIdx = minIdx;
                } else if (leftChildIdx < this.arr.length && this.arr[currentIdx] > this.arr[leftChildIdx]) {
                    [this.arr[currentIdx], this.arr[leftChildIdx]] = [this.arr[leftChildIdx], this.arr[currentIdx]];
                    currentIdx = leftChildIdx;
                } else if (rightChildIdx < this.arr.length && this.arr[currentIdx] > this.arr[rightChildIdx]) {
                    [this.arr[currentIdx], this.arr[rightChildIdx]] = [this.arr[rightChildIdx], this.arr[currentIdx]];
                    currentIdx = rightChildIdx;
                } else {
                    break;
                }
            }
            return root;
        }
    }

    for (let food of scoville) {
        Heap.insert(food);
    }

    if (Heap.arr[0] >= K) { return 0; }

    while (Heap.arr.length > 1) {
        answer++;

        const firstFood = Heap.delete();
        const secondFood = Heap.delete();
        Heap.insert(firstFood + secondFood * 2);
        
        if (Heap.arr[0] >= K) { return answer; }
    }

    return -1;
}

 

 

주저리

고난이.... 정말... 많았고..... 많았다..... 업 버블링 다운 버블링 둘 다 구현은 금방 했는데 업 버블링은 정상이었고 다운 버블링이 뭔가 이상했다. 내가 틀린 부분은 1. 자식 노드가 존재하는지 검사를 안 함. 2. 자식 둘 다 작으면 더 작은 자식이랑 바꿔야 하는데 이걸 모르고 그냥 왼쪽 자식이랑 바꿈. 그리고 힙 내용은 아니지만 틀린 부분은 음식 안 섞어도 처음부터 모든 스코빌 지수가 K 이상일 수 있음을 간과했다. 힙 구현은 2학년때 하고 처음 해서 우왕좌왕했다. 근데 코테 치러가서 힙 구현하려면 깔끔하게 포기하고 다른 문제 푸는 게 낫겠다는 생각이 들었다. 굳이 클래스로 구현하지도 않았고, 다운 버블링 코드도 상당히 지저분하다.