[알고리즘] Swift -백준 #11286(절댓값 힙)

문제링크

https://www.acmicpc.net/problem/11286

11286번: 절댓값 힙

 

문제

절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.

1. 배열에 정수 x (x ≠ 0)를 넣는다.
2. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

입력

첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 정수는 -231보다 크고, 231보다 작다.

출력

입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 절댓값이 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.

 

---

분석

배열에 x를 넣는다

배열에서 절댓값이 가장 작은 값을 출력, 그 값은 제거

만약 절댓값이 가장 작은 값이 여러 개면 가장 작은 수를 출력하고 그 값을 배열에서 제거한다.

 

풀이 과정

n = 연산의 개수

n개 반복 = 연산에 대한 정보를 나타내는 정수 x

만약 x = 0 이면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거

아니면 배열에 x라는 값을 추가한다.

입력에서 0이면 답을 출력한다, 만약 배열이 비어있는 경우에는 0을 출력

 

풀이

우선순위큐 구현 출처: https://beenii.tistory.com/143 [끄적이는 개발노트:티스토리]

우선순위큐(최소힙) 클로저를 이용해서 절대값을 비교하여 같을 때 최소힙으로 정렬

class PriorityQueue<T> {
    private var heap: [T] = []
    private let comparing: (_ o1: T,_ o2: T) -> Bool
    
    init(_ comparing: @escaping (_ o1: T,_ o2: T) -> Bool) {
        self.comparing = comparing
    }
    
    func size() -> Int { heap.count }
    
    func isEmpty() -> Bool { heap.isEmpty }
    
    func clear() { heap.removeAll() }
    
    func peek() -> T? { heap.first }
    
    func push(_ value: T) {
        heap.append(value)
        if heap.count == 1 { return }
        var valueIndex = heap.count - 1
        var parentIndex = (valueIndex-1) / 2
        while !comparing(heap[parentIndex], heap[valueIndex]) {
            heap.swapAt(valueIndex, parentIndex)
            valueIndex = parentIndex
            parentIndex = (valueIndex-1) / 2
            if valueIndex == 0 { break }
        }
    }
    
    func pop() -> T? {
        if heap.count == 0 { return nil }
        if heap.count == 1 { return heap.removeFirst() }
        
        func isChildEmpty(_ value: Int,_ left: Int,_ right: Int) -> Bool {
            if heap.count <= left { return true }
            if heap.count > right { return false }
            if comparing(heap[value], heap[left]) { return true }
            heap.swapAt(value, left)
            return true
        }
        
        heap.swapAt(0, heap.count-1)
        let answer = heap.removeLast()
        
        var valueIndex = 0
        var leftIndex = valueIndex * 2 + 1
        var rightIndex = valueIndex * 2 + 2
        
        if isChildEmpty(valueIndex, leftIndex, rightIndex) { return answer }
        
        while !comparing(heap[valueIndex], heap[leftIndex]) || !comparing(heap[valueIndex], heap[rightIndex]) {
            let index = comparing(heap[leftIndex], heap[rightIndex]) ? leftIndex : rightIndex
            heap.swapAt(valueIndex, index)
            valueIndex = index
            leftIndex = valueIndex * 2 + 1
            rightIndex = valueIndex * 2 + 2
            
            if isChildEmpty(valueIndex, leftIndex, rightIndex) { break }
        }
        return answer
    }
}

let input = Int(readLine()!)!

let pq = PriorityQueue<Int>() {
	if abs($0) == abs($1) { 
    	return $0 < $1 
    }
    return abs($0) < abs($1)
}

for _ in 0..<input {
    let num = Int(readLine()!)!
    
    if num == 0 {
        //0이면 절댓값이 가장 작은 수 중에 가장 작은 수를 출력하고 제거
        //배열이 비어있을 경우에는 0출력
        let minNum = pq.pop()
        minNum == nil ? print("0") : print(minNum!)
        
    } else {
        //0이 아니면 배열에 추가
        pq.push(num)
    }
}

 

 

 

 

 

 

 

결과

 

 

알게된 점

우선순위 큐를 오랜만에 다시 상기하게 되었다.

구현해놓은 코드를 사용하고 스위프트의 클로저 활용으로 쉽게 처리 가능했다.

이제 절댓값 힙의 경우 빠르게 처리 가능!