초니로그

문제 URL

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

문제 설명 요약

• 최소힙을 활용하여 주어지는 연산 처리
• 단, 최소힙의 우선순위는 "절댓값이 작은 것, 절댓값이 같다면 값이 작은 것"

문제 풀이

• 최소힙 직접 구현 필요 (스위프트는 힙 자료구조 없음)
  • Heap :: push -> 추가되는 값을 힙 내 원소들과 비교하여 저장 
  • Heap :: pop -> 최소힙의 값(최상단 루트 값) 삭제 및 반환

Swift를 활용한 풀이

var heap = [0] // 1-based-index
let N = Int(readLine()!)!
for _ in 0..<N {
    let x = Int(readLine()!)!
    if(x == 0) { print(pop()) }
    else { push(x) }
}

// 힙에 원소 추가
// 1. 배열 맨 끝에 추가
// 2. 끝 인덱스 값을 시작으로 부모값과의 대소 비교 후, 부모값보다 작다면 스왑 수행
// 3. (2)번 작업을 idx가 1까지 줄어들기 전까지 진행함. 단, 그 이전에 부모값보다 큰 경우엔 탈출
func push(_ n: Int) {
    heap.append(n)
    if(heap.count == 2) { return }

    var idx = heap.count-1
    while(idx > 1) {
        let parent = idx/2
        if(abs(heap[idx]) > abs(heap[parent])) { break }
        else if(abs(heap[idx]) == abs(heap[parent]) && heap[idx] > heap[parent]) { break }
        heap.swapAt(idx,parent)
        idx = parent
    }
}

// 최소힙의 값 삭제(루트 삭제) 및 반환
// 1. 힙의 맨 끝의 값을 루트로 이동
// 2. 갱신된 루트값에 대하여 자식값 두 개와 비교 후, 더 작은 자식 값이 있는 경우 스왑 수행
// (2)번 작업을 자식 인덱스값이 배열 범위 내에 있는 경우에 한하여 진행. 단, 두 자식보다 부모의 값이 작은 경우엔 탈출
func pop() -> Int {
    if(heap.count == 1) { return 0 }

    let deletedValue = heap[1]
    heap[1] = heap[heap.count-1]
    heap.removeLast()

    var idx = 1
    while(2*idx < heap.count) {
        let left = 2*idx, right = 2*idx+1
        var minIdx = left
        if(right < heap.count && abs(heap[right]) < abs(heap[left])) { minIdx = right }
        else if(right < heap.count && abs(heap[right]) == abs(heap[left]) && heap[right] < heap[left]) { minIdx = right }

        if(abs(heap[idx]) < abs(heap[minIdx])) { break }
        else if(abs(heap[idx]) == abs(heap[minIdx]) && heap[idx] < heap[minIdx]) { break }
        
        heap.swapAt(idx,minIdx)
        idx = minIdx
    }
    return deletedValue
}