스위프트 코딩테스트 강좌, 절댓값 힙 구현하기

문제 설명

절댓값 힙은 다음과 같은 규칙을 따르는 자료구조입니다:

• 가장 먼저 삽입된 원소는 절댓값이 가장 작은 원소이다.
• 절댓값이 같다면, 원소의 값이 작은 것이 앞에 온다.

추가적으로, 절댓값 힙에서 지원해야 하는 연산은 다음과 같습니다:

1. 숫자를 힙에 삽입한다.
2. 힙에서 절댓값이 가장 작은 숫자를 꺼낸다.

입력은 여러 개의 명령으로 이루어지며, 각 명령은 숫자를 삽입하거나, 꺼내는 형태입니다. 힙이 비어있을 때는 0을 출력합니다.

입력 형식

입력은 여러 줄로 주어지며, 각 줄은 다음과 같은 형태를 가집니다:

            1
            -1
            0
            1
            2 아이비
            

출력 형식

각 꺼내기 명령에 대해 힙의 가장 위에 있는 값을 출력합니다.

문제 해결 과정

문제를 해결하기 위해 먼저 절댓값 힙의 구조를 정의하고, 이를 위한 자료구조를 선택하겠습니다. 상용구형으로 구현할 수 있는 주요 방법은 배열을 사용한 힙 구조입니다. 여기서 스위프트의 기본 자료구조인 Array를 활용할 것입니다.

1단계: 힙 구조 설계

절댓값 힙을 구현하기 위해 힙의 구조와 우선 순위를 정의해야 합니다. 우리는 우선 순위를 절댓값에 두고, 절댓값이 같을 경우 실제 숫자의 크기를 기준으로 우선 순위를 정해야 합니다. 이를 위해 Comparable 프로토콜을 채택한 튜플을 사용합니다.

2단계: 삽입 연산 구현

힙에 삽입할 때는 새로운 원소를 배열의 끝에 추가한 다음, 힙의 조건을 만족할 때까지 올라가게 해야 합니다. 이 과정을 ‘올리기’ 또는 ‘상향 조정(up-heap)’이라고 합니다.

3단계: 삭제 연산 구현

절댓값이 가장 작은 원소를 삭제하기 위해서는 루트 원소를 제거한 후 마지막 원소를 루트에 위치시키고, 다시 힙 조건을 만족할 때까지 아래로 내려가게 해야 합니다. 이 과정을 ‘내리기’ 또는 ‘하향 조정(down-heap)’이라고 합니다.

스위프트 코드 구현

이제 우리가 정리한 알고리즘을 바탕으로 실제 스위프트 코드를 살펴보겠습니다.

            import Foundation

            struct AbsoluteHeap {
                private var heap: [(value: Int, absolute: Int)] = []

                mutating func insert(_ value: Int) {
                    let absoluteValue = abs(value)
                    heap.append((value, absoluteValue))
                    upHeap(index: heap.count - 1)
                }

                mutating func pop() -> Int {
                    guard !heap.isEmpty else { return 0 }
                    let root = heap[0].value
                    heap[0] = heap.removeLast()
                    downHeap(index: 0)
                    return root
                }

                private mutating func upHeap(index: Int) {
                    var childIndex = index
                    let child = heap[childIndex]
                    var parentIndex = (childIndex - 1) / 2

                    while childIndex > 0 && (heap[parentIndex].absolute > child.absolute ||
                                              (heap[parentIndex].absolute == child.absolute && heap[parentIndex].value > child.value)) {
                        heap[childIndex] = heap[parentIndex]
                        childIndex = parentIndex
                        parentIndex = (childIndex - 1) / 2
                    }

                    heap[childIndex] = child
                }

                private mutating func downHeap(index: Int) {
                    var parentIndex = index
                    let count = heap.count

                    while true {
                        let leftChildIndex = 2 * parentIndex + 1
                        let rightChildIndex = 2 * parentIndex + 2
                        var candidateIndex = parentIndex

                        if leftChildIndex < count && (heap[leftChildIndex].absolute < heap[candidateIndex].absolute ||
                                                       (heap[leftChildIndex].absolute == heap[candidateIndex].absolute && heap[leftChildIndex].value < heap[candidateIndex].value)) {
                            candidateIndex = leftChildIndex
                        }
                        
                        if rightChildIndex < count && (heap[rightChildIndex].absolute < heap[candidateIndex].absolute ||
                                                        (heap[rightChildIndex].absolute == heap[candidateIndex].absolute && heap[rightChildIndex].value < heap[candidateIndex].value)) {
                            candidateIndex = rightChildIndex
                        }

                        if candidateIndex == parentIndex { break }
                        heap.swapAt(parentIndex, candidateIndex)
                        parentIndex = candidateIndex
                    }
                }
            }

            var absoluteHeap = AbsoluteHeap()
            let operations = [1, -1, 0, 1, 2]
            for op in operations {
                if op != 0 {
                    absoluteHeap.insert(op)
                } else {
                    print(absoluteHeap.pop())
                }
            }
            

테스트 케이스

테스트 케이스 1

스크립트에서 사용한 입력값: [1, -1, 0, 1, 2]

기대 출력: 1 (pop을 수행했을 때)

테스트 케이스 2

스크립트에서 사용한 추가 입력값: [2, -4, 0]

기대 출력: -4 (pop을 수행했을 때)

결론

이제 스위프트를 사용하여 절댓값 힙을 성공적으로 구현할 수 있게 되었습니다. 이번 강좌에서는 알고리즘의 본질, 자료구조 선택, 스위프트의 기본적인 문법과 구조를 활용해 힙의 삽입/삭제 과정을 구현했습니다. 이 구현을 통해 알고리즘 문제 해결에 대한 사전 지식을 탄탄히 쌓을 수 있기를 바랍니다.

앞으로도 다양한 알고리즘 문제를 함께 해결해 나가길 기대합니다!