백준 1933 스카이라인
17 Nov 2021다양한 풀이방법이 있겠지만 스위핑과 maxHeap을 활용한 해법으로 풀었다. 개인적으로 정말 어려웠던 문제이다…
- 먼저 모든 빌딩을 시작지점과 끝 지점을 구분지은뒤 (start, end, height) 형태로 배열에 저장한다.
- 시작 지점이라면 start로 빌딩 시작 지점을 end로 해당 빌딩의 끝 지점을 입력해준다.
- 끝 지점이라면 start = end = 빌딩 끝 지점으로 입력하여 start와 end만으로 시작 선분인지 끝 선분인지 알 수 있게 해준다.
- 다음과 같은 규칙으로 모든 선분을 정렬해준다.
- x 좌표가 낮은 것이 먼저오도록
- 만약 x좌표가 같다면 시작 선분이 끝 선분보다 먼저오도록
- 만약 x좌표도 같고 선분 종류도 같다면 시작선분일 경우 높이가 높은 것이 먼저, 끝 선분일 경우 높이가 낮은 것이 먼저오게한다.

-
이제 정렬된 배열을 앞에서부터 쭉 스위핑하면서 문제를 해결한다.
-
Start 지점일 경우
-
현재의 skyline 최고 높이보다 더 높을 경우 최고 높이를 업데이트 해주고 최종 결과에 해당 위치와 높이를 추가해준다.
-
어떤 경우든 시작 지점이 나타나면 MaxHeap에 추가해준다. (다음그림과 같이 시작 높이가 MaxHeap root보다 작더라도 후에 쓰일 수 있다.)
-
앞에서 동일한 위치에서 Start지점일 경우 높이가 큰 것이 먼저오게 한 이유도 작은 높이는 최종 결과에 반영하지 않기 위해서이다.

-
-
End 지점일 경우
-
MaxHeap에 존재하는 최댓값을 하나씩 빼면서 만약 End지점의 x좌표보다 작거나 같은 값이라면 Heap에서 제거해준다.
-
최종적으로 Heap이 비었다면 skyline을 0으로 Heap에 값이 남아있다면 그것이 현재 X축에서 가장 높은 빌딩의 높이가 될 것이기 때문에 해당 값으로 skyline을 업데이트 해준다. 그 후 해당 지점과 skyline 높이를 최종 결과에 반영한다.
-
이 때 skyline값이 이전과 동일해서 변하지 않았다면 최종결과에 반영하지 않는다 (높이가 변하지 않았으므로)

-
-
-
전체 코드
//
// 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)
}
}