[프로그래머스] Swift - 상담원 인원

https://school.programmers.co.kr/learn/courses/30/lessons/214288

프로그래머스

 

2024.01.15 기준 Level 3

 

알고리즘 공부를 위해 풀고 기록하는 글입니다!
참고만 해주시고 더 좋은 풀이법이 있다면 알려주세요!

 

아이디어

문제 조건

• 상담원(멘토)가 n명, 상담 유형이 k개 존재
• 각 상담 유형에는 최소 1명 이상의 멘토가 배정
• reqs에 상담을 요청한 참가자들 정보 제공
  • [a, b, c] 형태이며 a시간에 요청하여 b시간 만큼 상담을 하며 c 유형의 상담을 의미
• 멘토는 한 번에 1명의 참가자만 멘토링 가능
• 해당 유형에 모든 상담원이 모두 상담중이라면 참가자는 기다렸다가 프리한 상담원이 생기면 바로 상담 시작
• 이렇게 기다리는 시간의 합의 최솟값을 리턴하자

 

우선 제한사항에서 1 <= k <= 5, k <= n <= 20 으로 명시되어있다.

매우 작은 수이기 때문에 모든 경우의 수를 전부 탐색해도 시간 초과가 발생하지 않을 것이라는 것을 염두하고 시작했다.

 

기다리는 시간을 계산하기 전에 상담원 n명을 k개의 유형으로 어떻게 분배할지가 관건이다.

 

나는 n <= 20이라는 작은 수를 믿고 모든 경우의 수를 전부 구하는 방법을 사용하기로 했다.

 

즉, 5명의 멘토를 3개의 유형에 배정한다면 [[1, 1, 3], [1, 2, 2], [1, 3, 1], [2, 1, 2], [2, 2, 1], [3, 1, 1]] 이렇게 배정할 수 있다.

 

이처럼 n명을 k개로 분산시키는 로직이 필요한데 이러한 알고리즘을 정수 분할 또는 자연수 분할이라고 한다.

재귀를 사용하여 멘토 배정의 모든 경우의 수를 구한다.

 

 

이제 각 경우의 수에 대하여 기다리는 시간이 얼마나 나오는지 구하고 그 중에서 최솟값을 리턴하면 된다.

 

문제 조건을 잘 보면 참가자가 1번 유형의 상담을 원한다면 같은 1번 유형의 상담을 원하는 참가자들끼리만 대기 시간에 영향을 주게 된다.

즉, 2번 또는 3번 유형을 기다리는 참가자랑은 전혀 연관이 없어진다는 것이다.

 

따라서 reqs 배열을 최초 1회 순회하며 같은 유형의 상담을 원하는 사람들 정보를 미리 분리해둔다.

딕셔너리를 사용하여 저장했다. (key = 상담 유형, value = 이 유형에 신청한 참가자 명단)

 

이제 대기 시간을 계산하면 된다.

Queue를 사용하여 상담중인 멘토를 관리했다.

큐에는 상담이 완료될 시간을 넣게 된다.

 

만약 상담원이 2명이고 30, 50분에 끝나는 상담이 진행 중이라면 큐에는

[30, 50]이 들어가게 된다. (항상 오름차순으로 정렬 필요)

 

이제 40분에 신청자가 발생하면 모든 상담원이 상담 중이기 때문에 상담이 끝나길 기다려야 한다.

이 때 큐의 first 요소인 30과 비교하게 된다.

40-30 = 10 분을 기다리게 되고

만약 이 신청자가 20분짜리 상담을 요청한 것이라면 종료 시간이 60분이기 때문에

큐는 이제 [50, 60] 상태가 된다.

이런 식으로 모든 신청자를 순회하며 대기 시간을 더해나가면 된다.

 

 

풀이

1. distributeInAdviceKind 함수 구현

상담 종류에 멘토를 분배하는 함수이다.

// 멘토를 각 상담 유형에 분배하는 경우의 수 계산 (자연수 분할 알고리즘)
fileprivate func distributeInAdviceKind(_ n: Int, _ k: Int) -> [[Int]] {
    var result = [[Int]]()
    var currentDistribution = Array(repeating: 0, count: k)
    distributePeople(n, k, 0, &currentDistribution, &result)
    return result
}

fileprivate func distributePeople(_ n: Int, _ k: Int, _ startIndex: Int, _ currentDistribution: inout [Int], _ result: inout [[Int]]) {
    if k == 1 {
        currentDistribution[startIndex] = n
        result.append(currentDistribution)
        currentDistribution[startIndex] = 0
        return
    }
    
    for i in 1...(n-k+1) { // n-k+1은 특정 상담 종류에 넣을 수 있는 최대 인원 수
        currentDistribution[startIndex] = i
        distributePeople(n-i, k-1, startIndex+1, &currentDistribution, &result)
    }
    currentDistribution[startIndex] = 0
}

 

재귀를 활용하여 멘토들을 분배한다.

 

 

2. calculateWaitingTimes 함수 구현

임의의 멘토 분배 경우의 수에서 신청자들이 기다려야하는 시간을 구하는 함수이다.

fileprivate func calculateWaitingTimes(k: Int, reqsForAdviceKind: [Int: [[Int]]], distribution: [Int]) -> Int {
    var time = 0
    
    for i in 1...k {
        time += calculateWaitingTimes(reqs: reqsForAdviceKind[i, default: []], mentor: distribution[i-1])
    }

    return time
}

fileprivate func calculateWaitingTimes(reqs: [[Int]], mentor: Int) -> Int {
    var time = 0
    var q = [Int]() // 상담 끝나는 시간 큐 먼저 끝나는 시간이 앞으로 오게해야 함
    var cnt = mentor
    
    for req in reqs {
        if cnt >= 1 {
            q.append(req[0] + req[1])
            q.sort()
            cnt -= 1
            continue
        }
        
        if q.first! <= req[0] {
            q.removeFirst()
            q.append(req[0] + req[1])
            q.sort()
        } else {
            // 기다려야 함
            let first = q.removeFirst()
            time += first - req[0]
            q.append(first + req[1])
            q.sort()
        }
    }

    return time
}

 

distribution 이 멘토 분배 상황을 의미합니다. ([1,2,2]라면 1번 유형에 1명, 2번 유형에 2명, 3번 유형에 2명 배치)

반복문을 돌며 각 유형에서 발생하는 대기 시간을 구하여 총 대기 시간을 구합니다.

 

각 유형에서 발생하는 대기 시간을 구할 때는 Queue를 사용하여 상담 중인 상태를 저장했습니다.

(이 때 우선순위 큐를 사용하게 되면 시간 복잡도를 더 낮출 수 있습니다. 이 문제에서는 그냥 Queue를 써도 통과가 됩니다.)

 

 

3. solution 함수 구현

fileprivate func solution(_ k:Int, _ n:Int, _ reqs:[[Int]]) -> Int {
    let allDistributionCases = distributeInAdviceKind(n, k) // 멘토 분배 전체 경우의 수
    var reqsForAdviceKind = [Int: [[Int]]]()
    var result = Int.max
    
    for req in reqs {
        let kind = req[2]
        reqsForAdviceKind[kind, default: []].append(req)
    }
    
    for distribution in allDistributionCases {
        result = min(result, calculateWaitingTimes(k: k, reqsForAdviceKind: reqsForAdviceKind, distribution: distribution))
    }
    
    return result
}

 

앞서 구현한 함수들을 호출하여 결과를 도출합니다.

1. 멘토 분배하기

2. 멘토 분배 경우의 수에서 대기 시간 구하기

3. 2에서 구한 대기 시간 중에서 가장 작은 값 리턴하기

 

 

마무리

여러 문제들이 합쳐진 느낌이었습니다.

분배(재귀), 대기 시간 계산에 필요한 아이디어들이 순차적으로 필요했습니다.

그래도 순서대로 한 단계씩 해결하다 보면 어느새 정답을 구할 수 있는 좋은 문제였던 것 같습니다!!