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

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

코딩테스트 연습 - 입국심사

이분탐색

 

접근방법

어떤 것을 이분탐색 해야할지 찾아내는 게 어려운 문제였다.

이분탐색은 수들이 정렬되었다는 가정하에 적용할 수 있는 방법이라는 점을 주의해서 풀이하면 조금이나마 빨리 해결방법을 찾을 수 있지 않을까 싶다. 쨌든 도저히 모르겠어서 검색해서 힌트를 얻었다.

 

이 문제의 핵심은 심사하는데 걸리는 총시간을 기준으로 이분탐색을 진행하는 것이다.

그러니까 이분탐색의 범위가 1분 ~ 가장 비효율적으로 오래걸릴 때의 총 심사시간이다.

 

가장 비효율적인 총 심사시간은 times 배열에서 가장 큰 값이다.

즉, 1명을 심사하는 데 걸리는 시간이 가장 긴 심사관에게 n명 모두 심사를 받을 경우이다.

가장 오래 기다리고 가장 오래 심사하므로 이 경우에 가장 오래걸린다.

 

이 다음부터는 풀이가 쉬운데, 이분탐색의 원리를 적용하면 된다.

 

시작점과 끝점의 중간값은 검토하고자 하는 심사시간이다.

mid만큼의 시간(분)이 주어졌을 때 해당 시간 안에 각 심사관들이 심사할 수 있는 최대 인원을 모두 더한 값을 구한다.

이때 인원이 n명 보다 작으면 mid분 보다는 더 긴 시간이 필요하다는 뜻이므로 start 값을 mid+1로 한다.

이때 인원이 n명 보다 크거나 같으면 mid분이 우리가 원하는 최소 심사시간일 수도, 최소 심사시간보다 클 수도 있으므로

end 값을 mid로 한다.

 

이 과정을 start가 end와 같아질 때까지 반복한다.

그 후에 start 혹은 end값을 반환한다.

 

이분탐색은 무엇을 이분탐색할지 정하는 것도 어렵지만,

나는 늘 start와 end에 무엇을 대입하고, 마지막에 start를 반환할지, end를 반환할지, start-1을 반환할지 고민하는 데 시간을 더 쓴다.

문제 조건마다 다를 때가 많아서 차근차근 풀이하면 어렵지 않게 기준을 정할 수 있을거라고 생각한다.

 

소스코드

import Foundation

func solution(_ n:Int, _ times:[Int]) -> Int64 {
    guard let maxTime:Int = times.max() else { return 0 }
    
    var start:Int64 = 1
    var end:Int64 = Int64(maxTime * n)
    var mid:Int64 = (start + end)/2
    
    while start < end {
        mid = (start + end)/2
        var capableN:Int64 = times.reduce(0) { $0 + mid/Int64($1) }
        if capableN >= n {
            end = mid
        } else {
            start = mid+1
        }
    }
    
    return end
}