시작하며 🖐🏻

예... 이것도 힙으로 풀었습니다만...

정말 제게 유혹을 엄청 준 문제였어요.
딱 이걸 보자마자, 대충 느낌이 왔습니다.

아 이거, 그냥 정렬로 풀어도 뚫리겠다!

이게 가능한 게, 현재 프로그래머스로 문제를 푼지 1달이 채 안됐는데, 여기는 꽤나 테스트케이스가 허술(?)한 느낌이 많이 들더라구요.

그래서, 풀려다가... 결국 또 고집에 최소/최대힙으로 풀어야겠다!고 했었는데,
테스트 케이스 3번이 계속 통과가 안돼서 또 하루를 날렸어요...!

이에 대한 원인은 알고보니, 제가 weight 조정을 잘못했던 부분이었습니다 😰
여튼, 제 똥고집(?)을 앞세우며 결국 문제를 해결해냈어요!
만족하며, 코드를 리뷰해봅시다 🌈

풀이과정

저는 다음과 같은 문제 풀이방식을 생각해냈어요.

1. 정렬로 풀 수도 있겠지만, 그냥 힙을 만들어주자! 이때 기준은 최대힙이다.
2. Heap 클래스를 만들어주고, 최대힙에 관한 메서드를 만들어주는데, 이때 최소힙의 경우 각 value에 -1을 곱한다음 비교를 하면 결국 가장 큰 값이 최솟값이 되는 방식을 택한다!
3. 결과적으로 weight라는 가중치조정을 통해 한 힙에서 최대/최소힙을 빼오는 방식을 구현할 수 있게 된다.
4. 이때 주의해야 할 건, 힙의 경우 계속해서 트리를 업데이트하지 않기 때문에 root가 최댓값(최솟값)임을 보장하지만, 나머지의 대소관계를 보장하지는 않는다.
5. 따라서 계속해서 weight가 기존가 바뀔 때마다 업데이트해준다. 결과를 출력하면 결국 성공!

저는 4번까지는 괜찮았는데 5번의 과정에 있어서, 좀더 최적화를 시키려고 가중치가 바뀌지 않을 때는 그냥 업데이트 하지 않는 방식으로 구현했었는데, 이는 4번에 위배되나 봅니다 😂 결국 계속 업데이트하는 걸로...

class Heap {
    constructor() {
        this.heap = [ null ];
        this.weight = 1; // default: max;
    }
    swap(a, b) {
        [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
    }
    updateParentIndex(index) {
        return Math.floor(index / 2);
    }
    updateIndicies(index) {
        return [ index, index * 2, index * 2 + 1 ]
    }
    getLength() {
        return this.heap.length;
    }
    print() {
        console.log(this.heap, this.weight);
    }
    heapify() {
        const arr = [ ... this.heap ];
        this.heap = [];
        arr.forEach(value => this.heappush(value));
    }
    heappush(value) {
        this.heap.push(value);
        let nowIndex = this.heap.length - 1;
        let parentIndex = this.updateParentIndex(nowIndex);
        while (nowIndex > 1 && this.heap[nowIndex] * this.weight > this.heap[parentIndex] * this.weight ) {
            this.swap(nowIndex, parentIndex);
            nowIndex = parentIndex;
            parentIndex = this.updateParentIndex(nowIndex);
        }
    }
    heappop(weight) {
        if (this.heap.length === 1) return;
        if (this.heap.length === 2) return this.heap.pop();
        this.weight = weight;
        this.heapify();
        const result = this.heap[1];
        this.heap[1] = this.heap.pop();
        let [ nowIndex, leftIndex, rightIndex ] = this.updateIndicies(1);
        if (this.heap[leftIndex] === undefined) return result;
        if (this.heap[rightIndex] === undefined) {
            if (this.heap[leftIndex] * this.weight > this.heap[nowIndex] * this.weight) this.swap(leftIndex, nowIndex);
            return result;
        }
        if (this.heap[leftIndex] * this.weight > this.heap[nowIndex] * this.weight || this.heap[rightIndex] * this.weight > this.heap[nowIndex] * this.weight) {
            const updatedIndex = this.heap[leftIndex] * this.weight > this.heap[rightIndex] * this.weight ? leftIndex : rightIndex;
            this.swap(nowIndex, updatedIndex);
            [ nowIndex, leftIndex, rightIndex ] = this.updateIndicies(updatedIndex);
        }
        return result;
    }
    printResult() {
        if (this.heap.length === 1) return [0,0]
        else if (this.heap.length === 2) return [this.heap[1], this.heap[1]]
        else return [this.heappop(1), this.heappop(-1)]
    }
}


const solution = (operations) => {
    const heapq = new Heap();
    operations.forEach(operation => {
        const [ command, value ] = operation.split(" ");
        const intValue = parseInt(value);
        if (command === "I") heapq.heappush(intValue);
        else heapq.heappop(intValue);
        heapq.print()
    })
    return heapq.printResult()
};

마치며

결국 최적화는 못시켜서 결과는 불만스럽기는 한데... 어쨌든 문제는 해결했네요.
이제 어떻게 하면 좀 더 시간복잡도를 줄일지 고민해봐야겠어요...!