[백준/Swift] 1927 : 최소힙

문제

1927번: 최소 힙

간단한 문제 요약

 배열에 자연수를 넣는다. 입력값이 0이 나오면 배열에서 가장 작은 값을 출력하고 제거한다. 만약 배열에서 가장 작은 값을 출력 후 제거해야 하는데 비어있다면 0을 출력한다.

문제 풀이, 느낀점

 배열은 heap을 사용해서 따로 만들지 않았다. 매 입력마다 0일 때 heap에 원소가 있는지 없다면 0을 있다면 heap에서 pop된 값을 출력해 나가면 된다.

 추가로 print()함수를 매번 쓰는 것 보다 string으로 저장 후 출력하는게 빠르다는 것을 알게 됬다.

 

최소 힙 코드 리뷰를..

코드

var buffer: [UInt8] = Array(FileHandle.standardInput.readDataToEndOfFile()), byteIdx = 0; buffer.append(0)
@inline(__always) func readByte() -> UInt8 {
    defer { byteIdx += 1 }
    return buffer.withUnsafeBufferPointer { $0[byteIdx] }
}
@inline(__always) func readInt() -> Int {
    var number = 0, byte = readByte()
    while !(48...57 ~= byte) { byte = readByte() }
    while 48...57 ~= byte { number = number * 10 + Int(byte - 48); byte = readByte() }
    return number
}

//MARK: - Model
struct Heap<T> where T: Comparable {
    var list = [T]()
    let isLeftSmall: (T,T) -> Bool
    init(isLeftSmall: @escaping (T,T)->Bool) {
        self.isLeftSmall = isLeftSmall
    }
    init() {
        self.init(isLeftSmall: <)
    }
}
extension Heap {
    var isEmpty: Bool {
        return list.isEmpty
    }
    var count: Int {
        return list.count
    }
}
extension Heap {
    mutating func insert(_ element: T) {
        var idx = list.count
        list.append(element)
        while idx > 0 && isLeftSmall(list[idx],list[(idx-1)/2]) {
            list.swapAt(idx, (idx-1)/2)
            idx = (idx-1)/2
        }
    }
    mutating func delete() -> T? {
        guard !isEmpty else { return nil }
        guard count != 1 else { return list.popLast() }
        let element = list.first!
        list.swapAt(0, count-1)
        _ = list.removeLast()
        var idx = 0
        while idx < count {
            let (left,right) = (idx*2+1,idx*2+2)
            if right<count {
                if isLeftSmall(list[left],list[right]) && isLeftSmall(list[left],list[idx]) {
                    list.swapAt(left, idx)
                    idx = left
                } else if isLeftSmall(list[right],list[idx]) {
                    list.swapAt(right, idx)
                    idx = right
                } else {
                    break
                }
            }else if left<count{
                if isLeftSmall(list[left],list[idx]) {
                    list.swapAt(left, idx)
                    idx = left
                } else {
                    break
                }
            }else {
                break
            }
        }
        return element
    }
    
}

func solution() {
    var res = ""
    var minHeap = Heap<Int>()
    (0..<readInt()).forEach { _ in
        let value = readInt()
        if value == 0 {
            res += "\(minHeap.delete() ?? 0)\n"
        }else {
            minHeap.insert(value)
        }
    }
    print(res)
}

solution()