[프로그래머스] 이중우선순위큐 - Javascript

문제 설명 : https://school.programmers.co.kr/learn/courses/30/lessons/42628

프로그래머스

 

문제 요약 :

1. 최대, 최소 값 삭제, 숫자 삽입 명령 세 가지가 주어진다.
2.  모든 연산 이후 최대와 최솟값을 출력하라.

 

문제 풀이 시간 : 20분

문제 성공 여부 : 성공

 

 

접근 방법(성공) :

1. 일반 배열에 숫자를 계속 삽입한다.
2. 삭제 명령어 직전, 배열을 정렬하고 shift(), pop()으로 최소, 최대 값을 제거한다.

 

문제를 가만 생각해 보니 출제 의도와는 다른 허점을 발견하였다. (절대 힙을 구현하기 귀찮아서가 아니다.)

명령어의 최대 개수는 1,000,000개인데 이는 삽입과 삭제를 모두 합친 경우이다.

 

삭제할 때만 배열을 정렬하기 때문에 최악의 경우는 아마, 50만 개의 수를 삽입한 후 삭제 삽입을 50만 번 반복하는 경우다.

그럼 평균적으로 37만개의 데이터를 25만 번 정렬하는 건데.. 물론 시간초과는 나지만 힙을 구현하기엔 너무 귀찮았기 때문에 내가 생각한 로직을 먼저 구현해 보았다.

 

로직은 다음과 같다.

 

삽입 명령일 경우 num을 배열에 넣어준다.

이 경우 시간복잡도 최적화를 위한다면 삭제할 때만 정렬을 하면 된다. (난 코드 가독성을 위해 정렬을 매번 수행했다)

 

그리고 삭제 명령일 경우, num에 따라 shift(), pop() 중 하나를 수행해 주면 된다.

 

전체 코드(성공) :

function solution(operations) {
    const arr = [];
    for(const op of operations){
        const [cmd, num] = op.split(' ');
        if(cmd==="I"){
            arr.push(+num);
            arr.sort((a,b)=>a-b);
            continue;
        }
        
        if(num === "-1") arr.shift();
        else arr.pop();
    }
    
    return arr.length===0 ? [0,0] : [arr[arr.length-1], arr[0]];
}

 

와~

테스트케이스가 매우 허술한 문제였다.

 

찜찜한 마음을 갖고 다른 js 블로그들을 찾아보았다.

 

출처 : https://dev-russel.tistory.com/56

아니????????????????????

바로 js 선배님의 회초리를 맞아버렸다..

 

이 블로그의 따끔한 회초리를 맞고도 그냥 지나가면 안 되기에 다시 문제를 켰다.

 

 

접근 방법(힙을 구현하자..)

힙 클래스를 최근 최적화 시켜보았는데, 이에 대해선 조만간 블로그에 올릴 예정이다.

 

아무튼, 이 문제는 힙을 사용해서 풀이할 수 있다.

 

내가 생각한 로직은 다음과 같다.

 

1. maxHeap과 minHeap을 구현

2. 삽입 명령어일 경우 두 힙에 모두 삽입

3. 삭제 명령어에 따라 최댓값->maxHeap, 최솟값->minHeap을 pop 한다.

 

하지만, 이 방법에는 치명적인 문제점이 있다.

 

바로, 하나의 힙에만 삭제를 수행하게 되면 언젠가 다른 힙을 제거할 때 이미 삭제되었어야 할 데이터가 남아있게 된다.

예를 들어 2와 4를 삽입하고, -1 명령어를 두 번 실행한다.

그럼 minHeap은 2와 4를 순서대로 삭제하여 비어있게 된다.

하지만 maxHeap은 삭제 못하였기 때문에 다음 1 명령어에서 이미 삭제했던 4를 삭제하려 한다.

 

따라서, 우린 힙에서 삭제 연산을 할 때, 해당 숫자가 삭제되었는지 아닌지를 체크해줘야 한다.

 

Set를 사용할 수 있지만, 문제에선 숫자 중복의 가능성이 있다고 판단하여, Map으로 각 삽입된 숫자들의 남은 개수를 파악하고자 하였다.

 

class MinHeap{
    constructor(){
        this.heap = [null];
    }
    
    size(){
        return this.heap.length -1;
    }
    
    isEmpty(){
        return this.size()===0;
    }
    
    swap(a,b){
        [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
    }
    
    top(){
        return this.heap[1];
    }
    
    push(val){
        let curIdx = this.heap.length;
        this.heap.push(val);
        
        let parIdx = Math.floor(curIdx/2);
        
        while(parIdx>0 && this.heap[parIdx] > this.heap[curIdx]){
            this.swap(parIdx, curIdx);
            curIdx = parIdx;
            parIdx = Math.floor(curIdx/2);
        }
    }
    
    pop(){
        const min = 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;
        
        while(this.heap[leftIdx] < this.heap[curIdx] || this.heap[rightIdx] < this.heap[curIdx]){
            let minIdx = this.heap[leftIdx] > this.heap[rightIdx] ? rightIdx : leftIdx;
            this.swap(minIdx, curIdx);
            curIdx = minIdx;
            leftIdx = curIdx*2;
            rightIdx = curIdx*2+1;
        }
        return min;
    }
}

class MaxHeap{
    constructor(){
        this.heap = [null];
    }
    
    size(){
        return this.heap.length -1;
    }
    
    isEmpty(){
        return this.size()===0;
    }
    
    swap(a,b){
        [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
    }
    
    top(){
        return this.heap[1];
    }
    
    push(val){
        let curIdx = this.heap.length;
        this.heap.push(val);
        
        let parIdx = Math.floor(curIdx/2);
        
        while(parIdx>0 && this.heap[curIdx] > this.heap[parIdx]){
            this.swap(curIdx, parIdx);
            curIdx = parIdx;
            parIdx = Math.floor(curIdx/2);
        }
    }
    
    pop(){
        const max = 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;
        
        while(this.heap[leftIdx] > this.heap[curIdx] || this.heap[rightIdx] > this.heap[curIdx]){
            let minIdx = this.heap[leftIdx] < this.heap[rightIdx] ? rightIdx : leftIdx;
            this.swap(minIdx, curIdx);
            curIdx = minIdx;
            leftIdx = curIdx*2;
            rightIdx = curIdx*2+1;
        }
        return max;
    }
}


function solution(operations) {
    const map = new Map();
    const minHeap = new MinHeap();
    const maxHeap = new MaxHeap();
    
    // heap 정리
    const clean = (heap) => {
        while(!heap.isEmpty()){
            let top = heap.top();
            let leftNum = map.get(top);
            if(leftNum < 1) heap.pop();
            else break;
        }
    }
    
    for(const op of operations){
        const [cmd, num] = op.split(' ');
        if(cmd === "I"){
            if(map.has(+num)) map.set(+num, map.get(num)+1);
            else map.set(+num, 1);
            maxHeap.push(+num);
            minHeap.push(+num);
            continue;
        }
        
        clean(minHeap);
        clean(maxHeap);
        
        let delNum = num==="-1" ? minHeap.pop() : maxHeap.pop();
        let leftNum = map.get(delNum);
        map.set(delNum, leftNum-1);
    }
    
    clean(minHeap);
    clean(maxHeap);
    
    return minHeap.isEmpty() ? [0,0] : [maxHeap.pop(), minHeap.pop()];
}

 

삭제 시, 미리 minHeap과 maxHeap의 top을 꺼내보고, 삭제된 숫자라면 미리 제거를 해준다.

힙에 대해서는 다음 글에서 제대로 정리해 보겠다.