백준 Swift 최소 힙, 최대 힙, 절댓값 힙 (백준 Swift 1927번, 11279번, 11286번)

 

백준 Swift 힙(Heap) 세트 문제입니다.

 

절댓값 힙 문제는 총 3가지의 아이디어로 풀 수 있었습니다. (백준 11286번)

(idea 1 : 단순 값 비교 / idea 2 : 튜플 사용 / idea 3 : 최소힙과 최대힙을 동시 사용)

---

최소 힙 | 백준 Swift 1927번

관련 글 : https://developer-p.tistory.com/190

우선순위 큐 반례.txt

0.00MB

백준 1927번 MinHeap 반례 추가.

// MARK: - 1927번(최소 힙)
import Foundation

struct MinHeap<T: Comparable> {
    var heap: [T] = []
    
    var isEmpty: Bool {
        return heap.count <= 1 ? true : false
    }
    
    init() {}
    init(_ element: T) {
        heap.append(element) // 0번 index채우기 용
        heap.append(element) // 실제 Root Node 채움.
    }
    
    mutating func insert(_ element: T) {
        if heap.isEmpty {
            heap.append(element)
            heap.append(element)
            return
        }
        heap.append(element)
        
        func isMoveUp(_ insertIndex: Int) -> Bool {
            if insertIndex <= 1 { // Root Node일 때,
                return false
            }
            let parentIndex = insertIndex / 2
            return heap[insertIndex] < heap[parentIndex] ? true : false
        }
        
        var insertIndex = heap.count - 1
        while isMoveUp(insertIndex) {
            let parentIndex = insertIndex / 2
            heap.swapAt(insertIndex, parentIndex)
            insertIndex = parentIndex
        }
    }
    
    enum moveDownStatus { case left, right, none }
    
    mutating func pop() -> T? {
        if heap.count <= 1 {
            return nil
        }
        let returnData = heap[1]
        heap.swapAt(1, heap.count - 1)
        heap.removeLast()
        
        func moveDown(_ poppedIndex: Int) -> moveDownStatus {
            let leftChildIndex = poppedIndex * 2
            let rightChildIndex = leftChildIndex + 1
            
            // case1. 모든(왼쪽) 자식 노드가 없는 경우(완전이진트리는 왼쪽부터 채워지므로)
            if leftChildIndex >= heap.count {
                return .none
            }
            
            // case2. 왼쪽 자식 노드만 있는 경우
            if rightChildIndex >= heap.count {
                return heap[leftChildIndex] < heap[poppedIndex] ? .left : .none
            }
            
            // case3. 왼쪽&오른쪽 자식 노드 모두 있는 경우
            // case3-1. 자식들이 자신보다 모두 큰 경우(자신이 제일 작은 경우)
            if (heap[leftChildIndex] > heap[poppedIndex]) && (heap[rightChildIndex] > heap[poppedIndex]) {
                return .none
            }
            
            // case3-2. 자식들이 자신보다 모두 작은 경우(왼쪽과 오른쪽 자식 중, 더 작은 자식을 선별)
            if (heap[leftChildIndex] < heap[poppedIndex]) && (heap[rightChildIndex] < heap[poppedIndex]) {
                return heap[leftChildIndex] < heap[rightChildIndex] ? .left : .right
            }
            
            // case3-3. 왼쪽과 오른쪽 자식 중, 한 자식만 자신보다 작은 경우
            if (heap[leftChildIndex] < heap[poppedIndex]) || (heap[rightChildIndex] < heap[poppedIndex]) {
                return heap[leftChildIndex] < heap[rightChildIndex] ? .left : .right
            }
            
            return .none
        }
        
        var poppedIndex = 1
        while true {
            switch moveDown(poppedIndex) {
            case .none:
                return returnData
            case .left:
                let leftChildIndex = poppedIndex * 2
                heap.swapAt(poppedIndex, leftChildIndex)
                poppedIndex = leftChildIndex
            case .right:
                let rightChildIndex = (poppedIndex * 2) + 1
                heap.swapAt(poppedIndex, rightChildIndex)
                poppedIndex = rightChildIndex
            }
        }
    }
}

let N = Int(readLine()!)!
var myMinHeap: MinHeap<Int> = MinHeap()

for _ in 0..<N {
    let input = Int(readLine()!)!

    if input == 0 {
        let answer = myMinHeap.pop()
        answer == nil ? print("0") : print(answer!)
    }
    else {
        myMinHeap.insert(input)
    }
}

 

---

최대 힙 | 백준 Swift 11279번

관련 글 : https://developer-p.tistory.com/190

// MARK: - 11279번(최대 힙)
struct MaxHeap<T: Comparable> {
    var heap: [T] = []

    var isEmpty: Bool {
        heap.count <= 1 ? true : false
    }

    init() {}
    init(_ element: T) {
        heap.append(element)
        heap.append(element)
    }
    
    mutating func insert(_ element: T) {
        if heap.isEmpty {
            heap.append(element)
            heap.append(element)
            return
        }
        heap.append(element)
        
        func isMoveUp(_ insertIndex: Int) -> Bool {
            if insertIndex <= 1 { // rootNode
                return false
            }
            let parentIndex = insertIndex / 2
            return heap[insertIndex] > heap[parentIndex] ? true : false
        }
        
        var insertIndex: Int = heap.count - 1
        while isMoveUp(insertIndex) {
            let parentIndex = insertIndex / 2
            heap.swapAt(insertIndex, parentIndex)
            insertIndex = parentIndex
        }
    }
    
    enum moveDownStatus {case left, right, none}
    
    mutating func pop() -> T? {
        if heap.count <= 1 {
            return nil
        }
        let returnData = heap[1]
        heap.swapAt(1, heap.count - 1)
        heap.removeLast()
        
        func moveDown(_ poppedIndex: Int) -> moveDownStatus {
            let leftChildIndex = poppedIndex * 2
            let rightChildIndex = leftChildIndex + 1
            
            // case1. 모든(왼쪽) 자식 노드가 없는 경우, (완전이진트리는 왼쪽부터 채워지므로)
            if leftChildIndex >= heap.count {
                return .none
            }
            
            // case2. 왼쪽 자식 노드만 있는 경우,
            if rightChildIndex >= heap.count {
                return heap[leftChildIndex] > heap[poppedIndex] ? .left : .none
            }
            
            // case3. 왼쪽&오른쪽 자식 노드 모두 있는 경우
            // case3-1. 자식들보다 자신이 모두 큰 경우(자신이 제일 큰 경우)
            if (heap[poppedIndex] > heap[leftChildIndex]) && (heap[poppedIndex] > heap[rightChildIndex]) {
                return .none
            }
            
            // case3-2. 자식들이 자신보다 모두 큰 경우(왼쪽과 오른쪽 자식 중, 더 큰 자식을 선별)
            if (heap[poppedIndex] < heap[leftChildIndex]) && (heap[poppedIndex] < heap[rightChildIndex]) {
                return heap[leftChildIndex] > heap[rightChildIndex] ? .left : .right
            }
            
            // case3-3. 왼쪽과 오른쪽 자식 중, 한 자식만 자신보다 큰 경우, (= 둘 중 하나의 자식만 큰 경우)
            if (heap[leftChildIndex] > heap[poppedIndex]) || (heap[rightChildIndex] > heap[poppedIndex]) {
                return heap[leftChildIndex] > heap[rightChildIndex] ? .left : .right
            }
            return .none
        }
        
        var poppedIndex = 1
        while true {
            switch moveDown(poppedIndex) {
            case .none:
                return returnData
            case .left:
                let leftChildIndex = poppedIndex * 2
                heap.swapAt(leftChildIndex, poppedIndex)
                poppedIndex = leftChildIndex
            case .right:
                let rightChildIndex = poppedIndex * 2 + 1
                heap.swapAt(rightChildIndex, poppedIndex)
                poppedIndex = rightChildIndex
            }
        }
        
    }
    
}

let N = Int(readLine()!)!
var myMaxHeap: MaxHeap<Int> = MaxHeap()

for _ in 0..<N {
    let input = Int(readLine()!)!

    if input == 0 {
        let answer = myMaxHeap.pop()
        answer == nil ? print("0") : print(answer!)
    }
    else {
        myMaxHeap.insert(input)
    }
}

 

---

절댓값 힙 (1) | 백준 Swift 11286번

접근 아이디어 1 : 최소 힙에서, comparer를 활용해서 비교해주면 됨.

참고 : 글 아래 2번 풀이가 더 쉽고 간편하다.

 

(참고 : https://www.acmicpc.net/source/37235051)
// MARK: - 11286번(풀이 1 : comparer 추가)
struct MinHeap<T: Comparable> {
    var heap: [Int] = []
    
    var comparer: (Int, Int) -> Bool = {(a, b) in
        if abs(a) == abs(b) {
            return a > b
        }
        else {
            return abs(a) > abs(b)
        }
    }
    
    var isEmpty: Bool {
        return heap.count <= 1 ? true : false
    }
    
    init() {}
    init(_ element: Int) {
        heap.append(element) // 0번 index채우기 용
        heap.append(element) // 실제 Root Node 채움.
    }
    
    mutating func insert(_ element: Int) {
        if heap.isEmpty {
            heap.append(element)
            heap.append(element)
            return
        }
        heap.append(element)
        
        func isMoveUp(_ insertIndex: Int) -> Bool {
            if insertIndex <= 1 { // Root Node일 때,
                return false
            }
            let parentIndex = insertIndex / 2
//            return heap[insertIndex] < heap[parentIndex] ? true : false
            return comparer(heap[parentIndex], heap[insertIndex])
        }
        
        var insertIndex = heap.count - 1
        while isMoveUp(insertIndex) {
            let parentIndex = insertIndex / 2
            heap.swapAt(insertIndex, parentIndex)
            insertIndex = parentIndex
        }
    }
    
    enum moveDownStatus { case left, right, none }
    
    mutating func pop() -> Int? {
        if heap.count <= 1 {
            return nil
        }
        let returnData = heap[1]
        heap.swapAt(1, heap.count - 1)
        heap.removeLast()
        
        func moveDown(_ poppedIndex: Int) -> moveDownStatus {
            let leftChildIndex = poppedIndex * 2
            let rightChildIndex = leftChildIndex + 1
            
            // case1. 모든(왼쪽) 자식 노드가 없는 경우(완전이진트리는 왼쪽부터 채워지므로)
            if leftChildIndex >= heap.count {
                return .none
            }
            
            // case2. 왼쪽 자식 노드만 있는 경우
            if rightChildIndex >= heap.count {
//                return heap[leftChildIndex] < heap[poppedIndex] ? .left : .none
                return comparer(heap[poppedIndex], heap[leftChildIndex]) ? .left : .none
            }
            
            // case3. 왼쪽&오른쪽 자식 노드 모두 있는 경우
            // case3-1. 자식들이 자신보다 모두 큰 경우(자신이 제일 작은 경우)
//            if (heap[leftChildIndex] > heap[poppedIndex]) && (heap[rightChildIndex] > heap[poppedIndex]) {
            if (comparer(heap[leftChildIndex], heap[poppedIndex])) && (comparer(heap[rightChildIndex], heap[poppedIndex])) {
                return .none
            }
            
            // case3-2. 자식들이 자신보다 모두 작은 경우(왼쪽과 오른쪽 자식 중, 더 작은 자식을 선별)
//            if (heap[leftChildIndex] < heap[poppedIndex]) && (heap[rightChildIndex] < heap[poppedIndex]) {
            if (comparer(heap[poppedIndex], heap[leftChildIndex])) && (comparer(heap[poppedIndex], heap[rightChildIndex])) {
//                return heap[leftChildIndex] < heap[rightChildIndex] ? .left : .right
                return comparer(heap[rightChildIndex], heap[leftChildIndex]) ? .left : .right
            }
            
            // case3-3. 왼쪽과 오른쪽 자식 중, 한 자식만 자신보다 작은 경우
//            if (heap[leftChildIndex] < heap[poppedIndex]) || (heap[rightChildIndex] < heap[poppedIndex]) {
            if (comparer(heap[poppedIndex], heap[leftChildIndex])) || (comparer(heap[poppedIndex], heap[rightChildIndex])) {
//                return heap[leftChildIndex] < heap[rightChildIndex] ? .left : .right
                return comparer(heap[rightChildIndex], heap[leftChildIndex]) ? .left : .right
            }
            
            return .none
        }
        
        var poppedIndex = 1
        while true {
            switch moveDown(poppedIndex) {
            case .none:
                return returnData
            case .left:
                let leftChildIndex = poppedIndex * 2
                heap.swapAt(poppedIndex, leftChildIndex)
                poppedIndex = leftChildIndex
            case .right:
                let rightChildIndex = (poppedIndex * 2) + 1
                heap.swapAt(poppedIndex, rightChildIndex)
                poppedIndex = rightChildIndex
            }
        }
    }
}

let N = Int(readLine()!)!
var myAbsHeap: MinHeap<Int> = MinHeap()

for _ in 0..<N {
    let input = Int(readLine()!)!
    
    if input == 0 {
        let answer = myAbsHeap.pop()
        answer == nil ? print("0") : print(answer!)
    }
    else {
        myAbsHeap.insert(input)
    }
}

---

절댓값 힙 (2) | 백준 Swift 11286번

접근 아이디어 2 : 튜플을 (아래처럼 선언 뒤) 최소힙에 넣고, 튜플을 정렬시킨 뒤, 원본값을 출력한다.

튜플 : (절댓값, 원본값)

알게된 점 : 튜플도 정렬이 된다!

상세 설명

(오름차순 정렬 시) 앞의 값을 기준으로 먼저 정렬되고, 그 다음 뒤의 값을 기준으로 정렬된다.

즉,

이 문제의 조건인 (앞) 절대값을 기준으로 오름차순 정렬되고,

그 다음 (뒤) 원본값도 오름차순으로 (작은 것부터) 정렬되기 때문에,

최소힙에 튜플을 넣음으로써 쉽게 풀 수 있다.

 

 

// MARK: - 11286번(풀이 2 - 튜플을 넣어서 비교)
struct MinHeap<T: Comparable> {
    var heap: [(T, T)] = []
    
    var isEmpty: Bool {
        return heap.count <= 1 ? true : false
    }
    
    init() {}
    init(_ element: (T, T)) {
        heap.append(element) // 0번 index채우기 용
        heap.append(element) // 실제 Root Node 채움.
    }
    
    mutating func insert(_ element: (T, T)) {
        if heap.isEmpty {
            heap.append(element)
            heap.append(element)
            return
        }
        heap.append(element)
        
        func isMoveUp(_ insertIndex: Int) -> Bool {
            if insertIndex <= 1 { // Root Node일 때,
                return false
            }
            let parentIndex = insertIndex / 2
            return heap[insertIndex] < heap[parentIndex] ? true : false
        }
        
        var insertIndex = heap.count - 1
        while isMoveUp(insertIndex) {
            let parentIndex = insertIndex / 2
            heap.swapAt(insertIndex, parentIndex)
            insertIndex = parentIndex
        }
    }
    
    enum moveDownStatus { case left, right, none }
    
    mutating func pop() -> (T, T)? {
        if heap.count <= 1 {
            return nil
        }
        let returnData = heap[1]
        heap.swapAt(1, heap.count - 1)
        heap.removeLast()
        
        func moveDown(_ poppedIndex: Int) -> moveDownStatus {
            let leftChildIndex = poppedIndex * 2
            let rightChildIndex = leftChildIndex + 1
            
            // case1. 모든(왼쪽) 자식 노드가 없는 경우(완전이진트리는 왼쪽부터 채워지므로)
            if leftChildIndex >= heap.count {
                return .none
            }
            
            // case2. 왼쪽 자식 노드만 있는 경우
            if rightChildIndex >= heap.count {
                return heap[leftChildIndex] < heap[poppedIndex] ? .left : .none
            }
            
            // case3. 왼쪽&오른쪽 자식 노드 모두 있는 경우
            // case3-1. 자식들이 자신보다 모두 큰 경우(자신이 제일 작은 경우)
            if (heap[leftChildIndex] > heap[poppedIndex]) && (heap[rightChildIndex] > heap[poppedIndex]) {
                return .none
            }
            
            // case3-2. 자식들이 자신보다 모두 작은 경우(왼쪽과 오른쪽 자식 중, 더 작은 자식을 선별)
            if (heap[leftChildIndex] < heap[poppedIndex]) && (heap[rightChildIndex] < heap[poppedIndex]) {
                return heap[leftChildIndex] < heap[rightChildIndex] ? .left : .right
            }
            
            // case3-3. 왼쪽과 오른쪽 자식 중, 한 자식만 자신보다 작은 경우
            if (heap[leftChildIndex] < heap[poppedIndex]) || (heap[rightChildIndex] < heap[poppedIndex]) {
                return heap[leftChildIndex] < heap[rightChildIndex] ? .left : .right
            }
            
            return .none
        }
        
        var poppedIndex = 1
        while true {
            switch moveDown(poppedIndex) {
            case .none:
                return returnData
            case .left:
                let leftChildIndex = poppedIndex * 2
                heap.swapAt(poppedIndex, leftChildIndex)
                poppedIndex = leftChildIndex
            case .right:
                let rightChildIndex = (poppedIndex * 2) + 1
                heap.swapAt(poppedIndex, rightChildIndex)
                poppedIndex = rightChildIndex
            }
        }
    }
}

let N = Int(readLine()!)!
var myMinHeap: MinHeap<Int> = MinHeap()

for _ in 0..<N {
    let input = Int(readLine()!)!
    
    if input == 0 {
        let answer = myMinHeap.pop()
        answer == nil ? print("0") : print(answer!.1) // 튜플의 뒷부분(원본값) 출력.
    }
    else {
        myMinHeap.insert((abs(input), input))
    }
}

---

절댓값 힙 (3) | 백준 Swift 11286번

접근 아이디어 3

minHeap : 양수 - 양수일 땐, 절댓값이 작은 게 원본값도 작다. -> 따라서 minHeap에서 pop하면, 절댓값이 가장 작은 게 튀어나온다.

maxHeap : 음수 - 음수일 땐, 절댓값이 작은 게 원본값이 크다. -> 따라서 maxHeap에서 pop하면, 절댓값이 가장 작은 게 튀어나온다.

흐름1) 근데 만약, pop한 값이 둘 다 같으면 -> 음수가 들어 있는 maxHeap값을 pop해줘야 함.(원본값이 작은 걸 먼저 출력해야 하기 때문에)

흐름2) 둘 중 하나의 heap이 비어 있으면, 값이 있는 heap에서 pop을 해주면 됨.

흐름3) 둘 다 비어 있으면, 0을 출력 해주면 됨.

 

// MARK: - 11286번(풀이 3 : minHeap과 maxHeap을 사용)
// minHeap : 양수 - 양수일 땐, 절댓값이 작은 게 원본값도 작다. -> 따라서 minHeap에서 pop하면, 절댓값이 가장 작은 게 튀어나온다.
// maxHeap : 음수 - 음수일 땐, 절댓값이 작은 게 원본값이 크다. -> 따라서 maxHeap에서 pop하면, 절댓값이 가장 작은 게 튀어나온다.
// 흐름1) 근데 만약, pop한 값이 둘 다 같으면 -> 음수가 들어 있는 maxHeap값을 pop해줘야 함.(원본값이 작은 걸 먼저 출력해야 하기 때문에)
// 흐름2) 둘 중 하나의 heap이 비어 있으면, 값이 있는 heap에서 pop을 해주면 됨.
// 흐름3) 둘 다 비어 있으면, 0을 출력 해주면 됨.
struct MinHeap<T: Comparable> {
    var heap: [T] = []

    var isEmpty: Bool {
        return heap.count <= 1 ? true : false
    }

    init() {}
    init(_ element: T) {
        heap.append(element) // 0번 index채우기 용
        heap.append(element) // 실제 Root Node 채움.
    }

    mutating func insert(_ element: T) {
        if heap.isEmpty {
            heap.append(element)
            heap.append(element)
            return
        }
        heap.append(element)

        func isMoveUp(_ insertIndex: Int) -> Bool {
            if insertIndex <= 1 { // Root Node일 때,
                return false
            }
            let parentIndex = insertIndex / 2
            return heap[insertIndex] < heap[parentIndex] ? true : false
        }

        var insertIndex = heap.count - 1
        while isMoveUp(insertIndex) {
            let parentIndex = insertIndex / 2
            heap.swapAt(insertIndex, parentIndex)
            insertIndex = parentIndex
        }
    }

    enum moveDownStatus { case left, right, none }

    mutating func pop() -> T? {
        if heap.count <= 1 {
            return nil
        }
        let returnData = heap[1]
        heap.swapAt(1, heap.count - 1)
        heap.removeLast()

        func moveDown(_ poppedIndex: Int) -> moveDownStatus {
            let leftChildIndex = poppedIndex * 2
            let rightChildIndex = leftChildIndex + 1

            // case1. 모든(왼쪽) 자식 노드가 없는 경우 (완전이진트리는 왼쪽부터 채워지므로)
            if leftChildIndex >= heap.count {
                return .none
            }

            // case2. 왼쪽 자식 노드만 있는 경우
            if rightChildIndex >= heap.count {
                return heap[leftChildIndex] < heap[poppedIndex] ? .left : .none
            }

            // case3. 왼쪽&오른쪽 자식 노드 모두 있는 경우
            // case3-1. 자식들이 자신보다 모두 큰 경우(자신이 제일 작은 경우)
            if (heap[leftChildIndex] > heap[poppedIndex]) && (heap[rightChildIndex] > heap[poppedIndex]) {
                return .none
            }

            // case3-2. 자식들이 자신보다 모두 작은 경우(왼쪽과 오른쪽 자식 중, 더 작은 자식을 선별)
            if (heap[leftChildIndex] < heap[poppedIndex]) && (heap[rightChildIndex] < heap[poppedIndex]) {
                return heap[leftChildIndex] < heap[rightChildIndex] ? .left : .right
            }

            // case3-3. 왼쪽과 오른쪽 자식 중, 한 자식만 자신보다 작은 경우
            if (heap[leftChildIndex] < heap[poppedIndex]) || (heap[rightChildIndex] < heap[poppedIndex]) {
                return heap[leftChildIndex] < heap[rightChildIndex] ? .left : .right
            }

            return .none
        }

        var poppedIndex = 1
        while true {
            switch moveDown(poppedIndex) {
            case .none:
                return returnData
            case .left:
                let leftChildIndex = poppedIndex * 2
                heap.swapAt(poppedIndex, leftChildIndex)
                poppedIndex = leftChildIndex
            case .right:
                let rightChildIndex = (poppedIndex * 2) + 1
                heap.swapAt(poppedIndex, rightChildIndex)
                poppedIndex = rightChildIndex
            }
        }
    }
}

struct MaxHeap<T: Comparable> {
    var heap: [T] = []

    var isEmpty: Bool {
        heap.count <= 1 ? true : false
    }

    init() {}
    init(_ element: T) {
        heap.append(element)
        heap.append(element)
    }
    
    mutating func insert(_ element: T) {
        if heap.isEmpty {
            heap.append(element)
            heap.append(element)
            return
        }
        heap.append(element)
        
        func isMoveUp(_ insertIndex: Int) -> Bool {
            if insertIndex <= 1 { // rootNode
                return false
            }
            let parentIndex = insertIndex / 2
            return heap[insertIndex] > heap[parentIndex] ? true : false
        }
        
        var insertIndex: Int = heap.count - 1
        while isMoveUp(insertIndex) {
            let parentIndex = insertIndex / 2
            heap.swapAt(insertIndex, parentIndex)
            insertIndex = parentIndex
        }
    }
    
    enum moveDownStatus {case left, right, none}
    
    mutating func pop() -> T? {
        if heap.count <= 1 {
            return nil
        }
        let returnData = heap[1]
        heap.swapAt(1, heap.count - 1)
        heap.removeLast()
        
        func moveDown(_ poppedIndex: Int) -> moveDownStatus {
            let leftChildIndex = poppedIndex * 2
            let rightChildIndex = leftChildIndex + 1
            
            // case1. 모든(왼쪽) 자식 노드가 없는 경우, (완전이진트리는 왼쪽부터 채워지므로)
            if leftChildIndex >= heap.count {
                return .none
            }
            
            // case2. 왼쪽 자식 노드만 있는 경우,
            if rightChildIndex >= heap.count {
                return heap[leftChildIndex] > heap[poppedIndex] ? .left : .none
            }
            
            // case3. 왼쪽&오른쪽 자식 노드 모두 있는 경우
            // case3-1. 자식들보다 자신이 모두 큰 경우(자신이 제일 큰 경우)
            if (heap[poppedIndex] > heap[leftChildIndex]) && (heap[poppedIndex] > heap[rightChildIndex]) {
                return .none
            }
            
            // case3-2. 자식들이 자신보다 모두 큰 경우(왼쪽과 오른쪽 자식 중, 더 큰 자식을 선별)
            if (heap[poppedIndex] < heap[leftChildIndex]) && (heap[poppedIndex] < heap[rightChildIndex]) {
                return heap[leftChildIndex] > heap[rightChildIndex] ? .left : .right
            }
            
            // case3-3. 왼쪽과 오른쪽 자식 중, 한 자식만 자신보다 큰 경우, (= 둘 중 하나의 자식만 큰 경우)
            if (heap[leftChildIndex] > heap[poppedIndex]) || (heap[rightChildIndex] > heap[poppedIndex]) {
                return heap[leftChildIndex] > heap[rightChildIndex] ? .left : .right
            }
            return .none
        }
        
        var poppedIndex = 1
        while true {
            switch moveDown(poppedIndex) {
            case .none:
                return returnData
            case .left:
                let leftChildIndex = poppedIndex * 2
                heap.swapAt(leftChildIndex, poppedIndex)
                poppedIndex = leftChildIndex
            case .right:
                let rightChildIndex = poppedIndex * 2 + 1
                heap.swapAt(rightChildIndex, poppedIndex)
                poppedIndex = rightChildIndex
            }
        }
        
    }
    
}

let N = Int(readLine()!)!
var myMinHeap: MinHeap<Int> = MinHeap()
var myMaxHeap: MaxHeap<Int> = MaxHeap()

for _ in 0..<N {
    let input = Int(readLine()!)!

    if input > 0 { // 양수일 때,
        myMinHeap.insert(input)
    }
    else if input < 0 { // 음수일 때,
        myMaxHeap.insert(input)
    }
    else { // input이 0일 때,
        if myMinHeap.isEmpty == false { // 최소힙에 값이 있을 때,
            if myMaxHeap.isEmpty == false { // 최대힙에도 값이 있다면,
                let a = myMinHeap.pop()!
                let b = myMaxHeap.pop()!
                myMinHeap.insert(a) // 비교를 위해 빠진 값은 다시 추가.
                myMaxHeap.insert(b) // 비교를 위해 빠진 값은 다시 추가.
                
                if abs(a) < abs(b) { // a는 어차피 양수라 abs필요 없음.
                    print(myMinHeap.pop()!)
                }
                else { // 값이 같을 때에도, maxHeap(음수)쪽에서 빼줘야 함.
                    print(myMaxHeap.pop()!)
                }
            }
            else if myMaxHeap.isEmpty { // 최대힙엔 값이 없다면,
                print(myMinHeap.pop()!)
            }
        }
        else if myMinHeap.isEmpty { // 최소힙에 값이 없을 때,
            if myMaxHeap.isEmpty == false { // 최대힙에 값이 있으면,
                print(myMaxHeap.pop()!)
            }
            else if myMaxHeap.isEmpty { // 최대힙에도 값이 없으면,
                print(0)
            }
        }
    }
}

 

---