문제

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

제한 사항

• scoville의 길이는 2 이상 1,000,000 이하입니다.
• K는 0 이상 1,000,000,000 이하입니다.
• scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

풀이 (시간초과 ver)

아이디어

• 스코빌의 길이가 점점 짧아지므로, 스코빌의 길이가 0보다 클 동안 다음 과정 수행한다.
  • 스코빌을 오름차순 정렬합니다.
  • 만약, 정렬된 스코빌의 첫번째 원소가 K 이상이라면 성공!
  • 아니라면, Array.prototype.splice() 메소드를 사용하여 앞에 2개를 짤라내서 배열 형태로 반환 받은 다음, 문제 조건에 맞게 섞어서 다시 스코빌에 push해준 후, answer를 증가시킨다

코드

function solution(scoville, K) {
    var answer = 0;
    //스코빌의 길이가 유효하는 동안 다음 과정 수행
    while(scoville.length) {
        //오름차순 정렬
        scoville.sort((a, b) => a - b);
        //모두 K이상이 되었다면 가장 첫번째꺼 검사해도 K 이상이어야함.
        if(scoville[0] >= K) break;
        
        let [x, y] = scoville.splice(0, 2);
        scoville.push(x + 2*y);
        answer++;
    }
    
    return answer;
}

풀이 (정답 ver)

아이디어

• 일단 스코빌의 길이가 최대 백만이고, 스코빌을 정렬(O(NlogN))하고 splice(O(N))하는 게 계속 반복되면 무조건 시간 초과가 뜨기 마련이지만 위에 코드를 그냥 해 봤다.
• 방향은 저게 맞는데 sort와 스코빌의 앞 두 개를 효율적으로 빼내려면 최소 힙을 사용하는 것이 맞다고 판단되었다. (자바스크립트는 힙을 기본적으로 지원해주지 않아서 힙 클래스 코드를 다 외워야겠다)

주의사항

heap에 남은 원소 개수와 heapDelete 연산의 횟수를 생각해보자.. heap에 남은 게 두 개도 안 되는데 heap에서 두 개를 빼내려고 하면 안 된다. 이 경우까지 처리해주면 모든 테케를 통과할 수 있다.

코드

class Heap {
    constructor() {
        this.heap = [null];
    }
    
    swap(a, b) {
        [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
    }
    
    peek() {
        return this.heap[1];
    }
    
    size() {
        return this.heap.length - 1;
    }
    
    heapInsert(value) {
        this.heap.push(value);
        
        let curIdx = this.heap.length - 1;
        let parentIdx = Math.floor(curIdx / 2);
        
        while(curIdx > 1 && this.heap[curIdx] < this.heap[parentIdx]) {
            this.swap(curIdx, parentIdx);
            
            curIdx = parentIdx;
            parentIdx = Math.floor(curIdx / 2);
        }
    }
    
    heapDelete() {
        let ret = this.heap[1];
        //맨끝에걸 맨 위로 가져오는 과정
        if(this.heap.length <= 2) this.heap = [null];
        else this.heap[1] = this.heap.pop();
        
        let curIdx = 1;
        let leftIdx = curIdx * 2;
        let rightIdx = curIdx * 2 + 1;
        
        //왼쪽자식이 없다는 것은 오른쪽 자식도 없다는 말. 더 이상 할 게 없음.
        if(!this.heap[leftIdx]) return ret;
        //오른쪽 자식만 없는 상황
        if(!this.heap[rightIdx]) {
            if(this.heap[leftIdx] < this.heap[curIdx]) {
                this.swap(leftIdx, curIdx);
            }
            return ret;
        }
        
        //왼쪽자식, 오른쪽자식 다 있다면 내려가는 로직 수행
        //내려가기 위해서는 왼쪽이든 오른쪽이든 현재보다 작아야 함
        while(this.heap[curIdx] > this.heap[leftIdx] || this.heap[curIdx] > this.heap[rightIdx]) {
            //둘 중 더 작은 것과 교환하면 된다.
            const minIdx = this.heap[leftIdx] > this.heap[rightIdx] ? rightIdx : leftIdx;
            
            this.swap(minIdx, curIdx);
            curIdx = minIdx;
            leftIdx = curIdx * 2;
            rightIdx = curIdx * 2 + 1;
        }
        return ret;
    }
}

function solution(scoville, K) {
    var answer = 0;
    var minHeap = new Heap();
    scoville.forEach(sco => minHeap.heapInsert(sco));
    
    //스코빌의 길이가 유효하는 동안 다음 과정 수행
    while(minHeap.peek() < K && minHeap.size() >= 2) {      
        let x = minHeap.heapDelete();
        let y = minHeap.heapDelete();
        minHeap.heapInsert(x + 2*y);
        answer++;
    }
    
    if(minHeap.peek() < K) return -1;
    
    return answer;
}

파이썬 코드

from heapq import heapify, heappush, heappop
def solution(scoville, K):
    heapify(scoville)
    iter = 0
    while scoville[0] < K:
        if len(scoville) >= 2:
            low = heappop(scoville)
            high = heappop(scoville)
            heappush(scoville, low + 2 * high)
            iter += 1
        else:
            break
 
    if scoville[0] >= K:
        return iter
    else:
        return -1