[Swift] 상담원 인원

[문제]

코딩테스트 연습 - 상담원 인원 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

[문제 풀이]

백트래킹 + 우선순위큐를 이용해서 풀 수 있는 문제였다.

 

우선 백트래킹을 이용해서 내가 정해줄 수 있는 멘토의 수를 모두 정한다.

k가 3이고 n이 5라면 (1,1,3), (1,2,2), (1,3,1), (2,1,2), (2,2,1), (3,1,1)의 6가지가 나오면 된다.

여기서 중요한것은 완전 탐색이 아닌 백트래킹이라는 점이다.

문제에서 보면 모든 멘토는 1부터 시작이고 멘토들을 모두 합친 값은 n이 나와야 한다.

즉, 벡터의 total이 n을 넘는순간 return으로 가지치기를 하는 백트래킹 유형이다.

 

func backTrack() -> Void{    
    if vec.count == k {
        if total != n {
            return
        }
        timeTable()
        return
    }

    for i in 1...n - k + 1 {
        if (total + i) > n {
            return
        }
        vec.append(i)
        total += i
        backTrack()
        total -= i
        vec.removeLast()
    }
}

 

위와 같은 코드를 사용해서 백트래킹을 할 수 있고 이제 해당 멘토들의 수를 알 수가 있으니 이 수를 이용해서 나올 수 있는 최소값이 몇인지 파악하는 함수를 만들자.

 

우선순위 큐를 구현해서 우선순위 큐로 이루어진 배열을 선언하자.

var pq = Array(repeating: Heap<Int>(sort: <), count: 10)

 

우선순위 큐인 pq에서 뒤에 있는 인덱스는 reqs[i][2] 즉, 몇번째 멘토한테 넣을지 파악하는 인덱스이고 종료시간이 빠른 순서부터 작업이 끝날테니 greater<int> 를 통하여 정렬을 해주었다.

 

이제 reqs 변수를 처음부터 끝까지 차례대로 방문하면서

1. 지금 넣어져 있는 우선순위 큐의 종료시간 보다 지금 타입의 시작 시간이 빠르다면 

2. 해당 타입의 멘토가 비어있다면

3. 만일 해당 타입의 멘토가 모두 차있다면

의 3가지 조건을 정해서 반복문을 돌려주자.

 

주의사항이 있다면 pq에 넣어야 하는건 종료시간이고 종료시간은 reqs[i][0] + reqs[i][1]이 아닐 수 있다는 것이다.

[회고]

발생할 수 있는 대기시간이 생각보다 크다. type이 5개에 시간이 1,000이 최고라 발생할 수 있는 대기시간이 1,000,000 이상이 안될줄 알았는데 테스트케이스 8번에서 문제가 발생해서 9,999,999로 통과를 하였다.

어딘가에서 발생하는 최대값 계산을 착각한 모양. 흔히 있을 수 있는 실수이니 어지간해선 최대값을 int의 한계인 20억으로 두자.

[코드]

import Foundation

//우선순위큐 구현
public struct Heap<T> {

    private var nodes = [T]()

    private var orderCriteria: (T, T) -> Bool

    public init(sort: @escaping (T, T) -> Bool) {
        self.orderCriteria = sort
    }

    public var count: Int {
        return nodes.count
    }

    public func top() -> T? {
        return nodes.first
    }

    func isEmpty() -> Bool {
        return nodes.isEmpty
    }

    public mutating func insert(_ value: T) {
        nodes.append(value)
        shiftUp(nodes.count - 1)
    }

    public mutating func remove() -> T? {
        guard !nodes.isEmpty else { return nil }

        if nodes.count == 1 {
            return nodes.removeLast()
        } else {
            let value = nodes[0]
            nodes[0] = nodes.removeLast()
            shiftDown(0)
            return value
        }
    }

    private func parentIndex(ofIndex i: Int) -> Int {
        return (i - 1) / 2
    }

    private func leftChildIndex(ofIndex i: Int) -> Int {
        return 2*i + 1
    }

    private func rightChildIndex(ofIndex i: Int) -> Int {
        return 2*i + 2
    }

    private mutating func shiftUp(_ index: Int) {
        var childIndex = index
        let child = nodes[childIndex]
        var parentIndex = self.parentIndex(ofIndex: index)

        while childIndex > 0 && orderCriteria(child, nodes[parentIndex]) {
            nodes[childIndex] = nodes[parentIndex]
            childIndex = parentIndex
            parentIndex = self.parentIndex(ofIndex: childIndex)
        }

        nodes[childIndex] = child
    }

    private mutating func shiftDown(from index: Int, until endIndex: Int) {
        let leftChildIndex = self.leftChildIndex(ofIndex: index)
        let rightChildIndex = leftChildIndex + 1

        var first = index
        if leftChildIndex < endIndex && orderCriteria(nodes[leftChildIndex], nodes[first]) {
            first = leftChildIndex
        }
        if rightChildIndex < endIndex && orderCriteria(nodes[rightChildIndex], nodes[first]) {
            first = rightChildIndex
        }
        if first == index { return }

        nodes.swapAt(index, first)
        shiftDown(from: first, until: endIndex)
    }

    private mutating func shiftDown(_ index: Int) {
        shiftDown(from: index, until: nodes.count)
    }
}

func solution(_ k:Int, _ n:Int, _ reqs:[[Int]]) -> Int {
    var answer = 9999999
    var total = 0
    var vec = [Int]()
    
    //백트래킹으로 구한 멘토 값에서 대기시간 구하는 함수
    func timeTable() -> Void{
        var mentor = vec
        var timeAnswer = 0
        var pq = Array(repeating: Heap<Int>(sort: <), count: 10)
        
        for req in reqs {
            var start = req[0]
            var duration = req[1]
            var type = req[2]
            if pq[type].isEmpty() == false && pq[type].top()! < req[0] {
                pq[type].remove()
                mentor[type - 1] += 1
            }
            if mentor[type - 1] >= 1 {
                pq[type].insert(start + duration)
                mentor[type - 1] -= 1
            }
            else if mentor[type - 1] <= 0 {
                var startTime = pq[type].top()!
                if start < startTime {
                    timeAnswer += startTime - start
                }
                pq[type].remove()
                pq[type].insert(startTime + duration)
            }
        }
        answer = min(timeAnswer,answer)
        return
    }
    
    //백트래킹
    func backTrack() -> Void{
        
        if vec.count == k {
            if total != n {
                return
            }
            timeTable()
            return
        }
        
        for i in 1...n - k + 1 {
            if (total + i) > n {
                return
            }
            vec.append(i)
            total += i
            backTrack()
            total -= i
            vec.removeLast()
        }
    }
    
    backTrack()
    return answer
}