[백준 Swift] 1927번 최소 힙

1927번 최소 힙

• 문제바로가기

풀이 방법

• 그냥 최소 힙을 구현하면 된다
• enum으로 max, min 두가지 경우로 나눠서 구현할 것이다

1. insert() 구현

• heapArray가 비어있을 때 삽입하려면, 0번 자리에 nil을 넣고 1번 자리에 삽입한다
  • 맨 앞에 nil을 넣는 이유는 인덱스를 맞추기 쉽게 하기 위함
• heapArray가 비어있지 않을 때 삽입하려면, 그냥 넣으면 된다
• 삽입한 후, 삽입한 값이 부모 노드의 값보다 클수(최소 힙의 경우: 작을수) 있으므로 moveUp()라는 메서드로 부모노드와 자식노드를 바꿀지 말지를 결정한다

2. moveUp() 구현

• 삽입된 값의 인덱스를 insertedIndex라 하면
• 이 값의 부모 노드의 인덱스는 insertedIndex / 2이다
• 만약 insertedIndex가 1보다 작거나 같다면 heapArray에 nil을 제외하면 1개의 노드만 존재하는 것이므로 moveUp()은 false를 반환하면 된다
• insertedIndex가 1보다 크면
  • max냐 min이냐에 따라 부모 노드의 값과 비교해서 바꿔야하면 true 아니면 false를 반환한다

3. pop() 구현

• 최상단의 노드를 꺼낸다(최상단의 노드의 인덱스 값은 1이다)
• 그리고 최상단 노드의 자리에 맨 마지막의 노드를 집어넣는다
• 그리고나서 moveDown() 메서드로 자리를 재배치할지 말지를 결정한다

4. moveDown() 구현

• case 1: left child 노드가 없는 경우 -> 바꾸지 않는다
• case 2: right child 노드가 없는 경우 -> left 노드랑만 비교한다
• case 3: left, right child 둘 다 있는 경우 -> left right를 비교하고 root 노드와 비교한다

---

풀이

Swift

struct Heap<T: Comparable> {
    
    enum Kind {
        case max
        case min
    }
    
    var heapArray = [T?]()
    let kind: Kind
    
    mutating func insert(_ value: T) {
        if heapArray.isEmpty {
            heapArray.append(nil)
            heapArray.append(value)
        } else {
            heapArray.append(value)
            
            var insertedIndex = heapArray.count - 1
            
            while moveUp(insertedIndex) {
                let parentIndex = insertedIndex / 2
                heapArray.swapAt(insertedIndex, parentIndex)
                insertedIndex = parentIndex
            }
        }
    }
    
    private func moveUp(_ insertedIndex: Int) -> Bool {
        if insertedIndex <= 1 {
            return false
        } else {
            let parentIndex = insertedIndex / 2
            
            switch kind {
            case .max:
                if heapArray[parentIndex]! < heapArray[insertedIndex]! {
                    return true
                }
                return false
            case .min:
                if heapArray[parentIndex]! > heapArray[insertedIndex]! {
                    return true
                }
                return false
            }
        }
    }
    
    mutating func pop() -> T? {
        if heapArray.count <= 1 {
            return nil
        }
        
        let popedData = heapArray[1]!
        heapArray[1] = heapArray.last!
        heapArray.removeLast()
        var popedIndex = 1
        
        while moveDown(popedIndex) {
            let leftChildIndex = popedIndex * 2
            let rightChildIndex = popedIndex * 2 + 1
            
            // case 2: right 노드가 없는 경우 -> left 노드랑만 비교한다
            if rightChildIndex >= heapArray.count {
                switch kind {
                case .max:
                    if heapArray[popedIndex]! < heapArray[leftChildIndex]! {
                        heapArray.swapAt(popedIndex, leftChildIndex)
                        popedIndex = leftChildIndex
                    }
                case .min:
                    if heapArray[popedIndex]! > heapArray[leftChildIndex]! {
                        heapArray.swapAt(popedIndex, leftChildIndex)
                        popedIndex = leftChildIndex
                    }
                }
            }
            // case 3: left right 둘다 있는 경우 -> left right를 비교하고 root 노드와 비교한다
            else {
                switch kind {
                case .max:
                    if heapArray[leftChildIndex]! > heapArray[rightChildIndex]! {
                        if heapArray[popedIndex]! < heapArray[leftChildIndex]! {
                            heapArray.swapAt(popedIndex, leftChildIndex)
                            popedIndex = leftChildIndex
                        }
                    } else {
                        if heapArray[popedIndex]! < heapArray[rightChildIndex]! {
                            heapArray.swapAt(popedIndex, rightChildIndex)
                            popedIndex = rightChildIndex
                        }
                    }
                case .min:
                    if heapArray[leftChildIndex]! > heapArray[rightChildIndex]! {
                        if heapArray[popedIndex]! > heapArray[rightChildIndex]! {
                            heapArray.swapAt(popedIndex, rightChildIndex)
                            popedIndex = rightChildIndex
                        }
                    } else {
                        if heapArray[popedIndex]! > heapArray[leftChildIndex]! {
                            heapArray.swapAt(popedIndex, leftChildIndex)
                            popedIndex = leftChildIndex
                        }
                    }
                }
            }
        }
        return popedData
    }
    
    private func moveDown(_ popedIndex: Int) -> Bool {
        
        let leftChildIndex = popedIndex * 2
        let rightChildIndex = popedIndex * 2 + 1
        
        // case 1: left 노드가 없는 경우 -> 바꾸지 않는다
        if leftChildIndex >= heapArray.count {
            return false
        }
        // case 2: right 노드가 없는 경우 -> left 노드랑만 비교한다
        else if rightChildIndex >= heapArray.count {
            switch kind {
            case .max:
                if heapArray[popedIndex]! < heapArray[leftChildIndex]! {
                    return true
                } else {
                    return false
                }
            case .min:
                if heapArray[popedIndex]! > heapArray[leftChildIndex]! {
                    return true
                } else {
                    return false
                }
            }
        }
        // case 3: left right 둘다 있는 경우 -> left right를 비교하고 root 노드와 비교한다
        else {
            switch kind {
            case .max:
                if heapArray[leftChildIndex]! > heapArray[rightChildIndex]! {
                    if heapArray[popedIndex]! < heapArray[leftChildIndex]! {
                        return true
                    } else {
                        return false
                    }
                } else {
                    if heapArray[popedIndex]! < heapArray[rightChildIndex]! {
                        return true
                    } else {
                        return false
                    }
                }
            case .min:
                if heapArray[leftChildIndex]! > heapArray[rightChildIndex]! {
                    if heapArray[popedIndex]! > heapArray[rightChildIndex]! {
                        return true
                    } else {
                        return false
                    }
                } else {
                    if heapArray[popedIndex]! > heapArray[leftChildIndex]! {
                        return true
                    } else {
                        return false
                    }
                }
            }
        }
    }
}

let n = Int(readLine()!)!
var heap = Heap(heapArray: [Int](), kind: .min)
for _ in 1...n {
    let x = Int(readLine()!)!
    if x == 0 {
        print(heap.pop() ?? 0)
    } else {
        heap.insert(x)
    }
}