상담원인원-Swift풀이

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

프로그래머스

오랜만입니다. 알고리즘은 계속 풀고 잇엇으나 그닥 올릴만한 것이 없어서...ㅜ (핑계핑계)

자 이번문제는 내가 PM이라고 몰입해야한다.

문제 분석

   1. 멘토에게 유형이 있음. 맞는 유형의 사람을 시간이 되면 한명씩 진행.
   2. 그런데 만약 여러명이 웨이팅중이다? 가장 먼저 상담요청한 참가자부터 진행한다.

   3.  req는 c번 유형의 사람이 a분때 b분만큼 요청하는 것을 의미한다.
    -> 결국 구해야하는것은 기다리는 시간을 최소로 하도록 멘토들을 인원배치를 잘해보자 (PM)

 

문제풀이

그런데 2번의 경우 어차피 req를 보면 시간이 오름차순으로 정렬을 해서 이미 주기에 따로 해줄 필요는 없을 것 같다.

결국 간단하게 보면 내 맘대로 멘토들의 수만큼 각각의 유형에 배치 후에 각각의 배치에 따른 시간을 구해준 후 최소의 시간을 구해주면 될꺼라 생각하였다.사실상 완탐이였다.

import Foundation

func solution(_ k:Int, _ n:Int, _ reqs:[[Int]]) -> Int {

    var timeTables = Array(repeating: [(Int,Int)](),count: k + 1 )
    for req in reqs {
        timeTables[req[2]].append((req[0],req[1]))
    }
    let permutations = permutationSum(k: k, targetSum: n)
    var minTime = Int.max
    for temp in permutations {
        let waitTime = calculateTotalWaitingTime(timeTables: timeTables, distribution: temp)
        minTime = min(minTime, waitTime)
    }

    return minTime
}
func calculateTotalWaitingTime(timeTables: [[(Int, Int)]], distribution: [Int]) -> Int {
    var totalTimes = 0 
     for (index, mentors) in distribution.enumerated() {
         let type = index + 1
         var waitQueue = [Int]()
         for (startTime , duration) in timeTables[type] {
             waitQueue = waitQueue.filter { $0 > startTime }
             if waitQueue.count < mentors {
                // 멘토가 여유가 있는 경우 즉시 상담
                waitQueue.append(startTime + duration)
            } else {
                // 멘토가 모두 바쁜 경우, 대기 시간을 추가하고 상담을 시작
                let earliestFinishTime = waitQueue.removeFirst()
                totalTimes += earliestFinishTime - startTime
                waitQueue.append(earliestFinishTime + duration)
            }
            waitQueue.sort() // 최솟값을 빠르게 찾기 위해 정렬
         }
     }
    return totalTimes
}
func permutationSum(k: Int, targetSum: Int) -> [[Int]] {
    var result = [[Int]]()
    func permute(current: [Int]) {
        // current 배열의 크기가 k가 되고, 합이 targetSum일 때 결과에 추가
        if current.count == k {
            if current.reduce(0, +) == targetSum {
                result.append(current)
            }
            return
        }

        // 숫자를 추가하여 다음 순열로 넘어가기
        for num in 1...targetSum {
            permute(current: current + [num])
        }
    }

    permute(current: [])
    return result
}

1.  조합생성: permutationSum 함수

이 함수는 주어진 targetSum을 k개의 멘토 유형으로 나누어 배치할 수 있는 모든 조합을 구합니다. 예를 들어, k = 3, targetSum = 5일 때, 가능한 조합 중 하나는 [1, 1, 3]입니다. 여기서 k는 유형의 개수이고, targetSum은 배치할 멘토의 총 수를 의미한다.

• 구현 과정:
  • current 배열을 만들어 멘토의 수를 순차적으로 추가해 나갑니다.
  • current의 크기가 k가 되고, 합이 targetSum일 때 조합에 추가합니다

2.  대기시간 계산: calculateTotalWaitingTime 함수

• 구현 과정:
  • • timeTables는 각 멘토 유형별로 요청 시간(startTime)과 걸리는 시간(duration)을 가지고 있습니다. distribution은 각 유형별 배정된 멘토 수를 나타냅니다.
    • 각 유형에 대해 waitQueue를 사용해 현재 상담 중인 멘토들의 종료 시간을 관리합니다.
      • 여유 있는 멘토가 있는 경우: waitQueue에 남아있는 멘토의 수가 요청보다 많다면 즉시 상담이 가능합니다.
      • 대기 중인 멘토가 없는 경우: 요청의 startTime이 waitQueue보다 크다면 상담 종료 후 다시 상담이 가능하기에 필터링을 통해 걸러줍니다.
      • 모든 멘토가 바쁜 경우: 가장 이른 종료 시간을 가진 멘토를 선택하여 대기 시간을 추가합니다.

3. 각 조합에 대기시간 계산 후 min값 리턴

 

---

시간복잡도

모든 조합을 생성하는 것때문에  시간복잡도는 O(n k승)이 된다. 별로 좋지 않는 알고리즘인 것 같다.... 근데 문제는 통과했다.

다른 사람들의 풀이를 보니 최적화를 위해서 크게 3가지의 방법이 있는 것 같다.

1. DP(..!!!!!! 깜짝놀랐다.. 이문제를 어캐 DP로 생각하지..?)

풀이과정을 살펴보면 마찬가지로 유형별로 분리를 한후, 중복조합을 통해 경우들을 구해준뒤 기다린 시간의 총합을 구하는 것인데!

각 과제에 멘토가 배정된 수에 따라 기다린 시간의 총합은 일정하므로 그 값을 재사용할 수 있도록 dp map에 저장해서 사용할 수 있다.

예를 들어, 어차피 우리가 모든 케이스에 대해 구해야 할텐데 그때마다 [1,1,3] , [1,2,2] 일텐데 1번 유형은 1명이 맡기에 시간은 이미 한번만 구해도 되기 때문이다. 

2. Greedy

우선 각 타입별로 사람을 1명씩 배치해 놓는다. 그 후 남은 멘토를 효율적으로 1명씩 분배하도록 while문을 통해 알고리즘을 구한다.

3. 백트래킹

순열을 구할때 백트래킹을 도입하여 이미 targetSum보다 합이 크면 리턴을 하여 조금 시간을 줄일 수 잇었다.

   func permute(current: [Int]) {
        if current.reduce(0,+) > targetSum {
            return
        }
   }

1.