문제
절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.
- 배열에 정수 x (x ≠ 0)를 넣는다.
- 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.
프로그램은 처음에 비어있는 배열에서 시작하게 된다.
입력
첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 정수는 -231보다 크고, 231보다 작다.
출력
입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 절댓값이 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.
내가 푼 풀이
- 최소힙 기반으로 정렬기준을 좀 바꾸면 된다.
- 절댓값이 같다면, 값이 작은게 우선인 힙을 만들면 된다.
import Foundation
struct Heap<T: Comparable> {
var elements: [T] = []
var sortFunction: (T,T) -> Bool
var isEmpty: Bool {
return elements.isEmpty || elements.count == 1
}
var peek: T? {
if elements.isEmpty {
return nil
} else {
return elements[1]
}
}
var count: Int {
if elements.isEmpty {
return 0
} else {
return elements.count - 1
}
}
init(elements: [T] = [], sortFunction: @escaping (T,T) -> Bool) {
if !elements.isEmpty {
self.elements = [elements.first!] + elements
} else {
self.elements = elements
}
self.sortFunction = sortFunction
if elements.count > 1 {
self.buildHeap()
}
}
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 swimUp(from index: Int) {
var idx = index
while idx != 1 && self.sortFunction(self.elements[idx], self.elements[parent(of: idx)]) {
self.elements.swapAt(idx, self.parent(of: idx))
idx = self.parent(of: idx)
}
}
mutating func insert(element: T) {
if self.elements.isEmpty {
self.elements.append(element)
self.elements.append(element)
return
}
self.elements.append(element)
self.swimUp(from: self.elements.endIndex - 1)
}
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(index, higherPriority)
self.diveDown(from: higherPriority)
}
}
mutating func buildHeap() {
for i in (1...(self.elements.count / 2)).reversed() {
self.diveDown(from: i)
}
}
mutating func remove() -> T? {
if self.isEmpty {
return nil
}
self.elements.swapAt(1, self.elements.endIndex - 1)
var returnValue = self.elements.removeLast()
self.diveDown(from: 1)
return returnValue
}
}
let N = Int(readLine()!)!
var heap = Heap(elements: [Int](),sortFunction: { if abs($0) == abs($1) {
return $0 < $1
} else {
return abs($0) < abs($1)
}})
for i in 0..<N {
let num = Int(readLine()!)!
if num == 0 {
if let poped = heap.remove() {
print(poped)
} else {
print(0)
}
} else {
heap.insert(element: num)
}
}
'코딩테스트 > 백준' 카테고리의 다른 글
BOJ-1920 수 찾기 Swift (0) | 2024.04.05 |
---|---|
BOJ-1002 터렛 Swift (0) | 2024.04.04 |
BOJ-11279 최대 힙 Swift (0) | 2024.04.04 |
BOJ-28279 덱 2 Swift (0) | 2024.04.03 |
BOJ-24511 queuestack Swift (1) | 2024.04.03 |