[Swift] 프로그래머스 입국심사

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

프로그래머스

 

1. 문제 이해

• 한 심사대에서는 한명만 심사 가능
• 가장 앞에서 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있다.
• 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사 받을 수 있다.
• 모든 사람이 심사를 받는데 걸리는 최소 시간을 구하라.

2. 설계

• 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하
• 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하
• 이분탐색
• 이분탐색은 기준 값(mid)을 무엇으로 할지, 어떤 기준으로 이분 탐색 범위를 정할 것인지 결정

2-1 심화 설계

기준값 정하기

• 최솟값(left), 최댓값(right) 찾기
• 심사관이 [7, 10]일 때 모든 사람이 심사시간 10을 가진 심사관에게만 심사를 받는 경우(최악의 경우)
• 최적의 경우 7분이 소요된다. - 1명만 심사 받아도 될 때
• 최악의 경우 60분이 소요된다. - n명 모두 10을 가진 심사관에게 심사 받을 때

이분탐색 범위 정하기

• mid = 33 = (7 + 60) / 2
• 33분일 때 [7, 10]인 심사관들에게 심사 받을 때 몇명까지 심사 받을 수 있을까?
• 33/7 = 4, 33 / 10 = 3이면 4+3 = 7명까지 심사 받을 수 있음
• mid 시간 동안 n 명을 초과한 인원을 심사 가능하다면 mid 시간이 너무 널널한 것
• mid 시간 동안 n 명 미만의 인원을 심사 가능하다면 mid 시간이 너무 부족한 것

• right = mid - 1 → mid = 19 = (7 + 32) / 2
• 19분 일 때 [7, 10]인 심사관들에게 심사 받을 때 몇명까지?
• 19/7 = 2, 19/10 = 1, 2+1 = 3명 mid 시간이 너무 부족하다….

 

• left = mid + 1 → mid = 26 = (20 + 32) / 2
• 26분 일 때 [7, 10]인 심사관들에게 심사 받을 때 몇명까지?
• 26/7 = 3, 26/10 = 2, 3+2 = 5명 mid 시간이 너무 부족하다….

 

• left = mid - 1 → mid = 28 = (27 + 32) / 2
• 28/7 = 4, 28/10 = 2, 4+2 = 6명 mid 시간에 n명만큼 심사가 가능하다!
• 일단 28분을 답으로 저장하되 혹시나 최소 시간이 더 있을까?
• right = mid - 1 → mid = 27 = (27+27) / 2
• 27/7 = 3, 27/10 = 2, 3+2 = 5명………..

3. 코드

import Foundation

func solution(_ n:Int, _ times:[Int]) -> Int64 {
    var left = Int64(times[0]) // 최솟값
    var right = Int64(times.max()! * n) // 최댓값
    var result = left
    while left <= right{
        var mid = (left + right) / 2
        
        var success: Int64 = 0 // mid 시간으로 몇명 심사 가능한지
        
        for time in times {
            success += mid / Int64(time)
        }
    
        if n > success{
            left = mid + 1
        }else {
            result = mid
            right = mid - 1
        }
    }
    return result
}
print(solution(6, [7, 10]))