[프로그래머스] 더 맵게 - JavaScript

1. 문제

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

프로그래머스

 

2. 풀이

• 처음에는 힙과 관련된 하나 없이 코드를 작성했다.

function solution(scoville, K) {
    let answer = 0;
    scoville.sort((a,b) => a-b); // scoviile 값을 오름차순으로 정렬 
    let underKCount = scoville.filter(item => item < K).length; // 정렬한 값에서 K 보다 작은 경우 확인.
    
    while(underKCount !== 0){ // K보다 작은 값이 없을 때까지 반복
    	//만약에 더이상 scoville을 K이상으로 만들 수 없다면 -1 리턴.
        if(scoville.length === 1 || scoville.length === 0) return -1;
        
        // answer 증가시키고
        answer++;
        
        // 가장 작은 값 뽑고, 두번째로 작은 값 뽑아냄.
        let firstMinVal = +scoville.splice(0, 1);
        let secondMinVal = +scoville.splice(0, 1);  
        
        // scoville에 섞은 값을 다시 넣은 후, 오름차순 정렬.
        scoville.push(firstMinVal + (secondMinVal * 2));
        scoville.sort((a,b) => a-b);
        
        // 다시 K보다 작은 값 계산.
        underKCount = scoville.filter(item => item < K).length;
    }
    
    return answer;
}

• 테스트 부분은 통과했지만, 효율성 테스트는 모두 시간 초과가 떴다.
• heap을 써보자.

function solution(scoville, K) {
    class MinHeap {
        constructor() {
            this.heap = [];
        }
        
        size() {
            return this.heap.length;
        }
        
        peek () {
            return this.heap[0];
        }
        
        push(value) {
            this.heap.push(value);
            this.heap.sort((a,b) => a-b);
        }
        
        pop() {
            if(this.heap.length === 0) return null;
            if(this.heap.length === 1) return this.heap.pop();
            
            const minVal = this.heap.shift();
            this.heap.sort((a,b) => a-b);
            return minVal;
        }
        
    }
    
    const minHeap = new MinHeap();
    scoville.forEach(s => {
        minHeap.push(s);
    });
    
    let answer = 0;
    while(minHeap.size() >= 2 && minHeap.peek() < K){
        const firstVal = minHeap.pop();
        const secondVal = minHeap.pop();
        const mixedVal = firstVal + secondVal * 2;
        minHeap.push(mixedVal);
        answer++;
    }
    
    return minHeap.peek() >= K ? answer : -1;
}

• 정렬부분을 sort()로 사용하니 여전히 효율성 부분을 통과하지 못하는 것 같다. 
• 정답코드

function solution(scoville, K) {
    class MinHeap {
        constructor() {
            this.heap = [];
        }
        
        size() {
            return this.heap.length;
        }
        
        peek () {
            return this.heap[0];
        }
        
        push(value) {
            this.heap.push(value);
            let index = this.heap.length - 1;

            while ( index > 0 && this.heap[index] < this.heap[Math.floor((index - 1) / 2)]) {
                const temp = this.heap[index];
                this.heap[index] = this.heap[Math.floor((index - 1) / 2)];
                this.heap[Math.floor((index - 1) / 2)] = temp;
                index = Math.floor((index - 1) / 2);
            }   
            
        }
        
        pop() {
            if(this.heap.length === 0) return null;
            if(this.heap.length === 1) return this.heap.pop();
            
            const minValue = this.heap[0];
            this.heap[0] = this.heap.pop();
            let index = 0;

            while (index * 2 + 1 < this.heap.length) {
                let minChildIndex = 
                  (index * 2 + 2 < this.heap.length 
                    && this.heap[index*2 + 2] < this.heap[index*2 + 1]) 
                    ? index * 2 + 2 : index * 2 + 1;

                if (this.heap[index] < this.heap[minChildIndex]) {
                    break;
                }

                const temp = this.heap[index];
                this.heap[index] = this.heap[minChildIndex];
                this.heap[minChildIndex] = temp;
                index = minChildIndex;
            }
            return minValue;
        }
    }
    
    const minHeap = new MinHeap();
    scoville.forEach(s => {
        minHeap.push(s);
    });
    
    let answer = 0;
    while(minHeap.size() >= 2 && minHeap.peek() < K){
        const firstVal = minHeap.pop();
        const secondVal = minHeap.pop();
        const mixedVal = firstVal + secondVal * 2;
        minHeap.push(mixedVal);
        answer++;
    }
    
    return minHeap.peek() >= K ? answer : -1;
}

 

3. 참고

• https://mingmeng030.tistory.com/293?category=884015

 

4. 정리

• 참고라고 써놓고 복붙해놨다........... class로 만들어서 푸는 문제는 여전히 부족함을 느낀다.  순서 정렬에서는 매번 sort()만 쓰다보니 직접 구현하기에 어려움이 많았다. 그래서 따라서 쳐보는 정도에 그쳐버렸다. 
• 코딩테스트가 이정도로 나온다면........ 아.....