[코딩테스트]백준 - 절댓값 힙(11286)

문제

절댓값 힙(11286)

해결한 코드

let fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
// let input = fs.readFileSync(__dirname + '/stdin.txt').toString().replace(/\r/g, "").trim().split('\n');
let n = +input[0]
let operations = []
for (let i = 1; i < input.length; i++) {
    operations.push(+input[i])
}

class AbsHeap {
    constructor() {
        this.nodes = []
    }

    insert(data) {
        this.nodes.push(data)
        this.bubbleUp()
    }

    setAbs(data) {
        return Math.abs(data)
    }

    bubbleUp(index = this.nodes.length - 1) {
        if (index < 1) return
        let currentNode = this.nodes[index]
        let parentIndex = Math.floor((index - 1) / 2)
        let parentNode = this.nodes[parentIndex]

        const absParent = this.setAbs(parentNode)
        const absCurrent = this.setAbs(currentNode)
        if (absParent < absCurrent) return
        if (absParent === absCurrent) {
            if (parentNode < currentNode) return
            this.nodes[index] = parentNode
            this.nodes[parentIndex] = currentNode
            index = parentIndex
        }
        this.nodes[index] = parentNode
        this.nodes[parentIndex] = currentNode
        index = parentIndex
        this.bubbleUp(index)
    }

    extract() {
        const absMin = this.nodes[0]
        if (this.nodes.length === 1) {
            this.nodes.pop()
            return absMin
        }
        this.nodes[0] = this.nodes.pop()
        this.trickleDown()
        return absMin
    }

    trickleDown(index = 0) {
        let leftChildIndex = index * 2 + 1
        let rightChildIndex = index * 2 + 2

        let current = index

        if (!this.nodes[leftChildIndex] && !this.nodes[rightChildIndex]) return

        const absLeftChild = this.setAbs(this.nodes[leftChildIndex])
        let absCurrent = this.setAbs(this.nodes[current])

        if (!this.nodes[rightChildIndex]) {
            // no right child
            if (absLeftChild < absCurrent) {
                current = leftChildIndex
            }
            if (absLeftChild === absCurrent) {
                if (this.nodes[leftChildIndex] < this.nodes[current]) {
                    current = leftChildIndex
                }
            }
        } else {
            // left, right child 
            const absRightChild = this.setAbs(this.nodes[rightChildIndex])
            if (absLeftChild > absRightChild) {
                // absleft > absright 
                if (absRightChild < absCurrent) {
                    current = rightChildIndex
                }
                if (absRightChild === absCurrent) {
                    if (this.nodes[rightChildIndex] < this.nodes[current]) {
                        current = rightChildIndex
                    }
                }
            } else if (absLeftChild === absRightChild) {
                //  absleft == absright 
                let t = this.nodes[leftChildIndex] - this.nodes[rightChildIndex]
                if (t > 0) {
                    // left > right 
                    if (absRightChild < absCurrent) {
                        current = rightChildIndex
                    }
                    if (absRightChild === absCurrent) {
                        if (this.nodes[rightChildIndex] < this.nodes[current]) {
                            current = rightChildIndex
                        }
                    } 
                } else {
                    // left <= right 
                    if (absLeftChild < absCurrent) {
                        current = leftChildIndex
                    }
                    if (absLeftChild === absCurrent) {
                        if (this.nodes[leftChildIndex] < this.nodes[current]) {
                            current = leftChildIndex
                        }
                    }
                }
            } else {
                // absleft < absright
                if (absLeftChild < absCurrent) {
                    current = leftChildIndex
                }
                if (absLeftChild === absCurrent) {
                    if (this.nodes[leftChildIndex] < this.nodes[current]) {
                        current = leftChildIndex
                    }
                }
            }
        }

        if (index !== current) {
            let t = this.nodes[current]
            this.nodes[current] = this.nodes[index]
            this.nodes[index] = t
            this.trickleDown(current)
        }
    }
}

const heap = new AbsHeap()
let answer = ''
operations.forEach((e, index) => {
    if (e !== 0) {
        heap.insert(e)
    } else {
        if (heap.nodes.length === 0) {
            answer += '0' + '\n'
        } else {
            let t = heap.extract()
            answer += t + '\n';
        }
    }
})

console.log(answer.trim())

풀이

※ 자료구조 힙을 이해한다.

1. 힙을 구현한다.

📌 생각해야 할 조건

• 부모 절댓값이 자식 절댓값보다 작으면? 문제 ㄴㄴ
• 부모 절댓값이 자식 절댓값보다 크면? 재정리 들어감
• 부모 절댓값이 자식 절댓값과 같으면?
  • 부모 노드가 자식 노드보다 작으면 문제 ㄴㄴ
  • 부모 노드가 자식 노드보다 크면 재정리 들어감

✔ 부모 노드는 자식 노드보다 절댓값이 작거나, (절댓값이 같으면) 실제 값이 작아야 한다.

1-1. 삽입

• 힙이 비어있으면? 그냥 push
• 비어있지 않으면?
  부모 노드와 비교하며 위의 조건에 맞는 자리를 찾아간다.

1-2. 삭제

• 힙이 비어있으면? 0 출력
• 힙의 길이가 1이면? 루트 노드 pop하고 return
• 힙의 길이가 1보다 크면?
  루트 노드 자리에 맨 마지막 원소를 놓고, 자식 노드와 비교하며 위의 조건에 맞는 자리를 찾아간다.

🚩 개인적으로 나는 이 부분 조건을 부족하게 달아줘서 통과하는데 오래걸렸다.

• 오른쪽 자식이 없는 경우
• 오른쪽 자식, 왼쪽 자식 둘 다 있는 경우
  • 왼쪽 자식 절댓값이 더 큰 경우
  • 두 자식의 절댓값이 같은 경우
    • 왼쪽 자식 노드가 오른쪽 자식 노드보다 큰 경우
    • 오른쪽 자식 노드가 왼쪽 자식 노드와 같거나 더 큰 경우
  • 오른쪽 자식의 절댓값이 더 큰 경우

위와 같이 조건을 세부적으로 나눈 다음,
해당 자식 노드의 절댓값과 현재 노드의 절댒값을 확인한다.
만약 절댓값이 같다면, 자식 노드보다 현재 노드가 더 작은지, 큰지 확인한다.

그래야만 진정한 제자리를 찾아갈 수 있다....

2. 연산에 따라 값을 출력한다.