요구능력
우선순위 큐 (힙)
문제풀이
힙과 우선순위 큐의 이론을 알고 생각하면서 따라쳐보시면 이해하기 쉽습니다.
저도 그렇게 익혔습니다.
sortFunction을 <로 할경우 최소힙, >로 할경우 최대힙이됩니다.
후기
우선순위큐, 힙에대해 알고있으면 풀리는 간단한문제
코드
import Foundation
struct Heap<T: Comparable> {
private var elements: [T] = []
private let sortFunction: (T, T) -> Bool
init (sortFunction: @escaping (T, T) -> Bool){
self.sortFunction = sortFunction
}
var isEmpty: Bool {
return self.elements.count == 1
}
func leftChild(of index: Int) -> Int {
return index * 2
}
func rightChild(of index: Int) -> Int {
return index * 2 + 1
}
func parent(of index: Int) -> Int {
return (index) / 2
}
mutating func diveDown(from index: Int) {
var higherPriority = index
let leftIndex = self.leftChild(of: index)
let rightIndex = self.rightChild(of: index)
if leftIndex < self.elements.endIndex && self.sortFunction(self.elements[leftIndex], self.elements[higherPriority]) {
higherPriority = leftIndex
}
if rightIndex < self.elements.endIndex && self.sortFunction(self.elements[rightIndex], self.elements[higherPriority]) {
higherPriority = rightIndex
}
if higherPriority != index {
self.elements.swapAt(higherPriority, index)
self.diveDown(from: higherPriority)
}
}
mutating func swimUp(from index: Int) {
var index = index
while index != 1 && self.sortFunction(self.elements[index], self.elements[self.parent(of: index)]) {
self.elements.swapAt(index, self.parent(of: index))
index = self.parent(of: index)
}
}
mutating func insert(node: T) {
if self.isEmpty {
self.elements.append(node)
return
}
self.elements.append(node)
self.swimUp(from: self.elements.endIndex - 1)
}
mutating func remove() -> T? {
if self.isEmpty { return nil }
self.elements.swapAt(1, elements.endIndex - 1)
let deleted = elements.removeLast()
self.diveDown(from: 1)
return deleted
}
}
var heap = Heap<Int>(sortFunction: <)
heap.insert(node: 0)
var str = ""
let n = Int(String(readLine()!))!
for _ in 0..<n{
let x = Int(String(readLine()!))!
if x > 0 {
heap.insert(node: x)
}else{
if let removed = heap.remove() {
str += "\(removed)\n"
}else{
str += "0\n"
}
}
}
print(str)
'Algorithm > 문제풀이_백준' 카테고리의 다른 글
[Swift][우선순위 큐] 백준 1655번 (가운데를 말해요) (0) | 2022.05.27 |
---|---|
[Swift][우선순위 큐] 백준 11286 (절댓값 힙) (0) | 2022.05.27 |
[Swift][이분탐색] 백준 1300번 (K번째 수) (0) | 2022.05.24 |
[Swift][이분 탐색] 백준 2110번 (공유기 설치) (0) | 2022.05.24 |
[Swift][이분탐색] 백준 2805번 (나무 자르기) (0) | 2022.05.24 |
댓글