Chapter 25: Priority Queue Challenges

Challenge 1: Array-based priority queue

이전에는 힙(heap)으로 큐(queue) 프로토콜(protocol)을 준수하여 우선 순위 큐(priority queue)를 구현했다. 배열(array)를 사용해 우선 순위 큐(priority queue)를 구현한다.

public protocol Queue {
    associatedtype Element
    
    mutating func enqueue(_ element: Element) -> Bool
    mutating func dequeue() -> Element?
    
    var isEmpty: Bool { get }
    var peek: Element? { get }
}

 

Solution

우선 순위 큐(priority queue)는 우선 순위 순서 대로 요소를 삭제(dequeue)한다. 우선 순위에 따라 최소(min) 혹은 최대(max) 우선 순위 큐(priority queue)가 될 수 있다. 배열(Array)기반 우선 순위 큐(priority queue)를 구현하려면 힙(Heap) 대신 배열(Array)을 사용해 큐(Queue) 프로토콜(protocol)을 구현하면 된다.

public struct PriorityQueueArray<T: Equatable>: Queue {
    private var elements: [T] = [] //heap 대신 array로 구현
    let sort: (Element, Element) -> Bool //정렬은 Queue 요소의 우선 순위를 결정한다.
}

이어서 initializer를 추가해 준다.

extension PriorityQueueArray {
    public init(sort: @escaping (Element, Element) -> Bool, elements: [Element] = []) {
        //initializer는 정렬 함수와 요소 배열을 사용한다.
        self.sort = sort
        self.elements = elements
        self.elements.sort(by: sort)
    }
}

Apple의 sort 함수의 시간 복잡도는 O(n log n)이다.

Swift의 sort 함수는 insertion sort(삽입 정렬)과 heap sort(힙 정렬)을 조합한 introsort를 사용한다.
https://github.com/apple/swift/blob/master/stdlib/public/core/Sort.swift

이어서 추가적인 구현을 해 준다.

extension PriorityQueueArray {
    public var isEmpty: Bool { 
        //Queue가 비어 있는지 확인한다.
        elements.isEmpty
    }
    
    public var peek: T? { 
        //Queue의 첫 요소를 확인한다.
        elements.first
    }
}

enqueue 메서드를 추가한다.

extension PriorityQueueArray {
    public mutating func enqueue(_ element: T) -> Bool {
        for (index, otherElement) in elements.enumerated() { //Queue의 모든 요소를 반복한다.
            if sort(element, otherElement) { //추가 하려는 요소의 우선 순위가 더 높은지 확인한다.
                elements.insert(element, at: index) //우선 순위가 더 높은 경우 현재 index에 삽입
                return true
            }
        }
        
        elements.append(element) 
        //요소가 Queue의 요소보다 우선 순위가 높지 않으면 요소를 끝에 추가한다.
        
        return true
    }
}

추가하는 새 요소(element)의 우선 순위(priority)를 확인하기 위해 모든 요소를 검토해야 하므로 enqueue의 시간 복잡도(time complexity)는 O(n)이다. 또한 배열(Array)의 요소(element) 사이에 삽입(insert)하는 경우, 요소(element)를 오른쪽으로 하나씩 이동해야 한다. 힙(Heap)처럼 트리(tree) 구조로 생각하지 않고 단순히 배열(Array)로 생각해야 한다. 이어서 dequeue를 구현한다.

extension PriorityQueueArray {
    public mutating func dequeue() -> T? {
        isEmpty ? nil : elements.removeFirst()
    }
}

배열(Array)의 요소(element)를 제거하기 전에 큐(Queue)가 비어있는지 확인해야 한다. dequeue 이후, 기존 요소를 왼쪽으로 하나씩 이동해야 하므로 O(n) 연산이다.  마지막으로 우선 순위 큐(priority queue) 출력을 위해, CustomStringConvertible를 구현한다.

extension PriorityQueueArray: CustomStringConvertible {
    public var description: String {
        String(describing: elements)
    }
}

구현을 확인해 본다.

var priorityQueue = PriorityQueueArray(sort: >, elements: [1, 12, 3, 4, 1, 6, 8, 7])
priorityQueue.enqueue(5)
priorityQueue.enqueue(0)
priorityQueue.enqueue(10)

while !priorityQueue.isEmpty {
    print(priorityQueue.dequeue()!)
    // 12
    // 10
    // 8
    // 7
    // 6
    // 5
    // 4
    // 3
    // 1
    // 1
    // 0
}

출력은 다음과 같다.

12
10
8
7
6
5
4
3
1
1
0

---

Challenge 2: Prioritize a waitlist

T-Swift 콘서트가 매진되어, 대기자 명단(waitlist)을 운용하고 있다. 하지만 티켓은 군 경력이 있는 사람을 우선하고, 그 다음으로 연령이 높은(seniority) 순서대로 판매한다. 대기자 명단에 있는 사람의 목록(list)을 우선 순위 기준으로 반환하는 함수를 작성한다. Person 구조체(struct)는 다음과 같다.

public struct Person: Equatable {
    let name: String
    let age: Int
    let isMilitary: Bool
}

 

Solution

다음 순서대로 우선 순위(priority)를 고려해 정렬(sort)해야 한다.

1. 군 경력
2. 연장자 순

해결 방법 중 하나로, 우선 순위 큐(priority queue) 자료구조(structure)를 사용해 이를 처리할 수 있다.

func tswiftSort(person1: Person, person2: Person) -> Bool { //두 요소를 비교한다.
    if person1.isMilitary == person2.isMilitary { 
        //둘 다 군 경력이 있다면 나이로 정렬한다.
        return person1.age > person2.age
    }
    
    return person1.isMilitary //군 경력이 있는 사람에 우선권을 준다.
}

위의 함수를 우선 순위 큐(priority queue)의 정렬(sort) 함수로 사용한다.

let p1 = Person(name: "Josh", age: 21, isMilitary: true)
let p2 = Person(name: "Jake", age: 22, isMilitary: true)
let p3 = Person(name: "Clay", age: 28, isMilitary: false)
let p4 = Person(name: "Cindy", age: 28, isMilitary: false)
let p5 = Person(name: "Sabrina", age: 30, isMilitary: false)

let waitlist = [p1, p2, p3, p4, p5]

var priorityQueue = PriorityQueue(sort: tswiftSort, elements: waitlist)

while !priorityQueue.isEmpty {
    print(priorityQueue.dequeue()!)
}

출력은 다음과 같다.

Person(name: "Jake", age: 22, isMilitary: true) 
Person(name: "Josh", age: 21, isMilitary: true) 
Person(name: "Sabrina", age: 30, isMilitary: false) 
Person(name: "Clay", age: 28, isMilitary: false) 
Person(name: "Cindy", age: 28, isMilitary: false)

---

Challenge 3: Minimize recharge stops

Swift-la는 새로운 전기차 회사로, 자동차가 지정된 목적지에 도달할 수 있는지 확인하는 기능을 추가하려 한다. 목적지까지 가는 도중에 충전소에 들를 수도 있다. 충전 횟수를 최소로 하면서, 목적지에 도달하는 경로를 찾기를 원한다.

 

문제 해결을 위해 다음과 같은 정보가 제공된다.

• target : 차량이 주행해야 하는 거리
• startCharge : 차량이 주행을 시작할 때 충전량
• stations : 주행 중 충전할 수 있는 충전소의 목록

ChargingStation 객체는 출발 위치로부터 얼만큼 떨어져 있는지를 나타내는 distance와 해당 충전소에서 충전할 수 있는 양을 나타내는 chargeCapacity 속성을 가지고 있다. 문제 해결을 위해 다음과 같은 가정을 한다.

1. 전기차는 충전 용량이 무한대이다.
2. 충전 단위 1으로 1마일을 주행할 수 있다.
3. 충전소의 목록은 출발 위치와의 거리를 기준으로 정렬되어 있다.

stations[0].distance < stations[1].distance < stations[k].distance

 

Solution

두 개의 엔티티(entity)가 주어진다. 하나는 충전소 정보를 나타내는 ChargingStation 이고,

struct ChargingStation {
    /// Distance from start location.
    let distance: Int
    /// The amount of electricity the station has to charge a car.
    /// /// 1 capacity = 1 mile
    let chargeCapacity: Int
}

또 하나는 차량이 목적지까지 주행 가능한지 여부를 나타내는 DestinationResult 이다.

enum DestinationResult {
    /// Able to reach your destination with the minimum number of stops.
    case reachable(rechargeStops: Int)
    /// Unable to reach your destination.
    case unreachable
}

마지막으로, minRechargeStops(_:) 함수가 주어진다. 이 함수의 매개변수(parameter)는 다음과 같다.

• target : 차량이 주행해야 하는 거리(마일)
• startCharge : 주행 전 출발 위치에서의 충전된 양
• stations : 거리 기준으로 정렬된 충전소 목록

정차할 최소 충전소 수를 찾기 위한 방법 중 하나는 우선 순위 큐(priority queue)를 사용하는 것이다.

func minRechargeStops(target: Int, startCharge: Int, stations: [ChargingStation]) -> DestinationResult {
    guard startCharge <= target else {
        //출발 지점에서 전기차의 충전량이 목표 주행 거리보다 크거나 같은 경우, 충전소에 들리지 않고도 목적지에 도착할 수 있다.
        return .reachable(rechargeStops: 0)
    }
    
    var minStops = -1 //목적지에 도착하는 데 필요한 최소 충전소 수를 트래킹한다.
    var currentCharge = 0 //주행 중 차량의 현재 충전량을 트래킹한다.
    var currentStation = 0 //현재까지 들린 충전소 수를 트래킹한다.
    var chargePriority = PriorityQueue(sort: >, elements:[startCharge])
    //들릴 수 있는 모든 충전소를 보유하고 있는 우선 순위 큐이다. 충전 용량이 가장 높은 충전소 부터 dequeue 된다.
    //Queue는 startCharge로 초기화된다.
    
    while !chargePriority.isEmpty { //우선 순위 큐 chargePriority는 가장 높은 충전 용량을 지닌 충전소를 우선순위로 한다.
        //chargePriority이 비어 있지 않다면, 도달 가능한 충전소가 있다는 의미이다.
        guard let charge = chargePriority.dequeue() else {
            //dequeue로 충전 용량이 가장 큰 충전소를 가져온다.
            return .unreachable
        }
        
        currentCharge += charge //차량 충전
        minStops += 1 //최소 충전소 수 증가
        
        if currentCharge >= target { //currentCharge로 목적지에 도착할 수 있는지 확인한다.
            return .reachable(rechargeStops: minStops) //도착할 수 있다면, 현재까지 들린 충전소 수를 .reachable과 반환한다.
        }
        
        while currentStation < stations.count && currentCharge >= stations[currentStation].distance {
            //현재 남은 충전량으로 목적지에 도달할 수는 없지만, 아직 남은 충전소가 있으며 다음 충전소까지 운행할 수 있다면
            let distance = stations[currentStation].chargeCapacity //충전소의 chargeCapacity
            _ = chargePriority.enqueue(distance) //우선 순위 큐에 거리를 추가한다.
            currentStation += 1
        }
    }
    
    return .unreachable //목적지에 도착할 수 없다.
}

구현한 함수의 우선 순위 큐(priority queue)는 도달 가능한 충전소 중 최대 용량을 가진 곳을 dequeue하는 욕심쟁이 알고리즘(greedy algorithm)이다. 구현을 확인해 본다.

let stations = [ChargingStation(distance: 10, chargeCapacity: 60),
                ChargingStation(distance: 20, chargeCapacity: 30),
                ChargingStation(distance: 30, chargeCapacity: 30),
                ChargingStation(distance: 60, chargeCapacity: 40)]

minRechargeStops(target: 100, startCharge: 10, stations: stations)

충전소를 최소 2번 들러야 함을 알 수 있다.