만득

코딩 공부 정리용

​

© 2021. All rights reserved.

백준 11286 절댓값 힙

23 Jun 2021

https://www.acmicpc.net/problem/11286

힙을 만드는데 최댓값, 최솟값이 아닌 절댓값이 가장 작은 값이 우선순위를 갖는 힙을 구성하는 문제이다. 물론 동일한 절댓값이면 음수가 양수보다 먼저 나오게 설정한다.

뭔가 엄청난 것을 할 필요없이 compare 함수만 제대로 설정해주면 끝이다. 그 외에는 알고리즘 설명에서 정리한 우선순위 큐를 그대로 사용하면 된다. 클로저를 사용해서 구현했으니 클로저에 대해 모른다면 문법공부를 하고오면 좋을 것 같다.

var minHeap = Heap<Int>{
    if abs($0) < abs($1) {
        return true
    }
    else if abs($0) == abs($1) {
        return $0 < $1
    }
    else {
        return false
    }
}

struct Heap<T> {
    var arr:[T]
    var compare:(T, T) -> Bool
    mutating func shiftUp(a: Int) {
        var index = a
        while index > 0 {
            let parent = (index-1)/2
            if compare(arr[index], arr[parent]) {
                arr.swapAt(index, parent)
                index = parent
            }
            else {
                break
            }
        }
    }
    mutating func shiftDown(a: Int) {
        var index = a
        var child = 2*a+1
        let count = arr.count
        while child < count {
            if child + 1 < count {
                child = compare(arr[child], arr[child+1]) ? child : child+1
            }
            if compare(arr[child], arr[index]) {
                arr.swapAt(index, child)
                index = child
                child = 2*index+1
            }
            else {
                break
            }
        }
    }
    mutating func insert(_ a: T) {
        arr.append(a)
        shiftUp(a: arr.count-1)
    }
    mutating func pop() -> T? {
        if arr.isEmpty {
            return nil
        }
        else {
            arr.swapAt(0, arr.count-1)
            let result = arr.removeLast()
            shiftDown(a: 0)
            return result
        }
    }
    init(arr: [T] = [], compare: @escaping (T, T) -> Bool) {
        self.arr = arr
        self.compare = compare
    }
}

var minHeap = Heap<Int>{
    if abs($0) < abs($1) {
        return true
    }
    else if abs($0) == abs($1) {
        return $0 < $1
    }
    else {
        return false
    }
}
let n = Int(readLine()!)!
for _ in 1...n {
    let k = Int(readLine()!)!
    if k == 0 {
        print(minHeap.pop() ?? 0)
    }
    else {
        minHeap.insert(k)
    }
}

Related posts