[백준] 1927-최소 힙

 

문제 URL

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

 

문제 설명 요약

• 최소힙을 활용하여 주어지는 연산 처리

 

문제 풀이

• 최소힙 직접 구현 필요 (스위프트는 힙 자료구조 없음)
  • Heap :: push -> 추가되는 값을 힙 내 원소들과 비교하여 저장 (부모는 자식 두 개보다 값이 작아야 함)
  • Heap :: root -> 최소힙의 최상단 루트 값 조회
  • Heap :: pop -> 최소힙의 값 삭제 (최상단 루트 값의 삭제)

 

Swift를 활용한 풀이

 

var heap = [-1] // 1-based index

let N = Int(readLine()!)!
for _ in 0..<N {
    let x = Int(readLine()!)!
    if x == 0 {
        print(root())
        pop()
    } else {
        push(x)
    }
}

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

    var idx = heap.count - 1
    while(idx > 1) { // 반복문 내에서 부모값을 조회하고자, /2를 수행하기 때문에 1보다 커야 함
        let parent = idx / 2
        if heap[parent] <= heap[idx] { break }
        heap.swapAt(parent, idx)
        idx = parent
    }
}

// 힙의 최상단 값 조회
func root() -> Int {
    return heap.count > 1 ? heap[1] : 0
}

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

    heap[1] = heap[heap.count - 1] // 마지막 요소를 루트에 복사
    heap.removeLast() // 마지막 요소 제거(제거하지 않으면 불필요한 끝값이 지속적으로 쌓여 더미가 커짐)

    var idx = 1
    while(2*idx < heap.count) {
        let left = 2 * idx
        let right = left + 1
        var minIdx = left

        if(right < heap.count && heap[right] < heap[left]) { minIdx = right }

        if heap[idx] <= heap[minIdx] { break }
        heap.swapAt(idx, minIdx)
        idx = minIdx
    }
}