백준 1933 스카이라인

문제 보러 가기

다양한 풀이방법이 있겠지만 스위핑과 maxHeap을 활용한 해법으로 풀었다. 개인적으로 정말 어려웠던 문제이다…

스크린샷 2021-11-18 오전 12 38 30

//
//  Created by 강현준 on 2021/11/17.
//

let INF = Int.max
let n = Int(readLine()!)!
var building: [(start: Int, end: Int, height: Int)] = []

(0..<n).forEach { index in
    let line = readLine()!.split(separator: " ").map { Int($0)! }
    building.append((line[0], line[2], line[1]))
    building.append((line[2], line[2], line[1]))
}

building.sort(by: {
    let firstFlag = $0.start == $0.end
    let secondFlag = $1.start == $1.end
    if $0.start != $1.start { return $0.start < $1.start }
    if firstFlag != secondFlag { return !firstFlag }
    return firstFlag ? $0.height < $1.height : $0.height > $1.height
})

var skyline = 0
var heap = MaxHeap<(end: Int, height:Int)>(compare: { $0.1 < $1.1 })
var result = ""

building.forEach { line in
    if line.start != line.end {
        if skyline < line.height {
            skyline = line.height
            result += "\(line.start) \(line.height) "
        }
        heap.insert((line.end, line.height))
    } else {
        while heap.root?.end ?? INF <= line.end { heap.pop() }
        if skyline != heap.root?.height ?? 0 {
            skyline = heap.root?.height ?? 0
            result += "\(line.end) \(skyline) "
        }
    }
}
print(result)


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