가장 큰 수 (Lv. 2)

문제 링크

풀이

import Foundation

func solution(_ numbers:[Int]) -> String {
    var priorityQueue = PriorityQueue()
    numbers.forEach {
        priorityQueue.enqueue($0)
    }
    
    var result = ""
    while let dequeue = priorityQueue.dequeue() {
        result = result + "\(dequeue)"
    }
    
    if result[result.startIndex] == "0" {
        return "0"
    }
    
    return result
}

struct PriorityQueue {
    var array: [Int] = []
    
    mutating func enqueue(_ num: Int) {
        array.append(num)
        shiftUp(array.count - 1)
    }
    
    mutating func dequeue() -> Int? {
        guard !array.isEmpty else {
            return nil
        }
        
        array.swapAt(0, array.count - 1)
        
        defer {
            shiftDown(0)
        }
        
        return array.removeLast()
    }
    
    mutating func shiftUp(_ childIndex: Int) {
        var child = childIndex
        var parent = parentIndex(childIndex)
        while child > 0 && sort(array[child], array[parent]) {
            array.swapAt(child, parent)
            child = parent
            parent = parentIndex(child)
        }
    }
    
    mutating func shiftDown(_ parentIndex: Int) {
        var parentIdx = parentIndex
    
        while true {
            var candidate = parentIdx
            let leftIdx = leftChildIndex(candidate)
            let rightIdx = rightChildIndex(candidate)

            if array.count > leftIdx && sort(array[leftIdx], array[candidate]) {
                candidate = leftIdx
            }

            if array.count > rightIdx && sort(array[rightIdx], array[candidate]) {
                candidate = rightIdx
            }

            if candidate == parentIdx {
                break
            } else {
                array.swapAt(parentIdx, candidate)
                parentIdx = candidate
            }
        }
    }
    
    func leftChildIndex(_ parentIndex: Int) -> Int {
        return parentIndex * 2 + 1
    }
    
    func rightChildIndex(_ parentIndex: Int) -> Int {
        return parentIndex * 2 + 2
    }
    
    func parentIndex(_ childIndex: Int) -> Int {
        return (childIndex - 1) / 2
    }
    
    // 비교 로직
    func sort(_ left: Int, _ right: Int) -> Bool {
        let leftFirst = Int("\(left)\(right)")!
        let rightFirst = Int("\(right)\(left)")!
        return leftFirst > rightFirst
    }
}

후기

정렬 방식에 대해서만 깊이 고민하면 되는 문제.
본인은 우선순위큐를 써서 풀었지만 그럴 필요는 없다...
enqueue/dequeue를 반복해서 할 필요가 없고 딱 한번만 전체 정렬시키면 되기 때문에 큐까지 쓰면서 코드 길게 할 필요는 없다.
다 풀고 다른 사람 풀이를 보니 코드 수 10줄도 안되서 간단하게 푸는걸 보고 허망했던 문제 큽..