[Swift] 프로그래머스 Lv3 상담원 민원

https://school.programmers.co.kr/learn/courses/30/lessons/214288?language=swift

프로그래머스

 

1. 문제이해

• n명의 상담사, k개의 상담 유형으로 이루어진 채용 설명회
• 각 멘토는 한 개의 상담 유형만 담당 가능, 같은 시간에 한 명의 참가자와 상담 가능
• 각 유형 별로 최소 1명의 멘토가 배치
• 모든 참가자의 대기 시간이 최소가 되도록 상담 유형별로 멘토를 정해야 함
• 모든 참가자 대기 시간 총합을 구하라
• 선입 선출 구조로 상담이 이루어진다.

 

2. 접근방법

[참가자가 상담하는 순서, 그리디]

1. 상담을 요청한 시각에 즉시 상담이 가능한 경우
2. 참가자가 상담을 위해 대기 해야 하는 경우 → (대기 시간 발생)
3. 상담이 빨리 끝나는 순으로 참가자를 상담사와 매칭

[상담사 인원 배치, 완전탐색]

1. 각 유형별 1명 씩 배치
2. 백트래킹으로 완전 탐색

3. 코드

func solution(_ k:Int, _ n:Int, _ reqs:[[Int]]) -> Int{
		// reqs -> [a,b,c] a분에 b분동안 c번 유형의 상담을 요청
    var counseler = Array(repeating: 1, count: k) // 각 유형별 상담사 인원, 초기 각 1명
    var result = Int.max

    func calculateWaitTime(typeCounts: [Int]) -> Int{
        var totalWaitTime = 0
        for type in 1...k{
            let typeReqs = reqs.filter{$0[2] == type}            
            let counselerCount = typeCounts[type - 1]
            var availableTimes = Array(repeating: 0, count: counselerCount) // 각 상담사 별 상담 끝나는 시각
            
            for req in typeReqs{
                let start = req[0] // 상담 요청 시각
                let duration = req[1] // 상담 시간
                
                availableTimes.sort() // 가장 먼저 상담이 끝나는 멘토 찾기
                let earliestAvailable = availableTimes[0]
                
                let waitTime = max(earliestAvailable - start, 0) // 대기 시간 계산
                totalWaitTime += waitTime
                
                // 상담 종료 시간 업데이트
                availableTimes[0] = max(start, earliestAvailable) + duration
            }
        }
        return totalWaitTime
    }
    
    // 백트래킹
    func dfs(remaining: Int, index: Int){
        if index == k {
            result = min(result, calculateWaitTime(typeCounts: counseler))
            return
        }
       
        for add in 0...remaining{
            counseler[index] += add
            dfs(remaining: remaining - add, index: index + 1)
            counseler[index] -= add
        }
    }
    // 상담원(n) - 상담 유형(k) = 상담 유형에 추가 배치할 수 있는 상담원
    dfs(remaining: n-k, index: 0)

    
    return result
}