[고득점 Kit (이분탐색)] 입국심사 (Python, Swift)

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

 

풀이

 해당 문제가 이분탐색을 활용해야 하는지 여부는 문제의 제한사항을 잘 살펴봐야 한다. 제한사항을 보면 입국심사를 기다리는 사람이 최대 10억명이고 각 심사관이 한 명을 심사하는데 걸리는 시간은 최대 10억분이라고 주어져 있다. 문제에서 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 구하라고 하였는데 제한사항을 봤을 때 이분탐색을 활용해야 하는 문제라고 생각할 수 있어야 한다(이분탐색 문제라는 것을 알고 풀기 시작했지만!)

 

 어쨌든 문제에서 심사에 걸리는 시간의 최솟값을 구하라고 하였기 때문에 심사에 걸리는 시간을 기준으로 잡아주었다. 그럼 이제 시작점과 끝점을 구해줘야 하는데 시작점은 times[0]으로 설정했고 끝점은 times의 마지막 원소에 n을 곱한 값으로 설정하였다. 그 후 while 반복문에서 mid를 설정하여 각 심사관에게 mid분이 주어졌을 때 총 몇 명을 입국심사를 할 수 있는지 구하였다(mid / time). 예를 들어 20분이 주어졌을 때 7분이 걸리는 심사관은 2명을 심사할 수 있다.

 

 이렇게 mid분에 총 몇 명을 심사할 수 있는지 확인하여 해당 값이 n명 이상일 경우에는 끝점을 변경하였고 n명 미만일 경우에는 시작점을 변경하였다.

 

코드

[Python]

def solution(n, times):
    left = times[0] # 시작점
    right = times[len(times) - 1] * n # 끝점
    res = 0 # 결과

    while left <= right:
        mid = (left + right) // 2 # mid분이 주어졌을 때
        cnt = 0 # 심사 가능한 총 인원 수

        # 각 심사관마다 mid분에 몇 명을 심사할 수 있는지 카운트
        for time in times:
            cnt += mid // time
        
        # n명 이상 심사 가능할 경우 더 짧은 시간을 찾기 위해 right를 mid-1로 변경
        # n명 미만일 경우 가능한 시간을 찾기 위해 left를 mid+1로 변경
        if cnt >= n:
            res = mid
            right = mid - 1
        else:
            left = mid + 1
    
    return res

[Swift]

import Foundation

func solution(_ n:Int, _ times:[Int]) -> Int64 {
    
    var left: Int64 = Int64(times[0]) // 시작점
    var right: Int64 = Int64(times[times.count - 1]) * Int64(n) // 끝점
    var res: Int64 = 0 // 결과
    
    while left <= right {
        let mid: Int64 = (left + right) / 2 // mid분이 주어졌을 때
        var cnt: Int64 = 0 // 심사 가능한 총 인원 수
        
        // 각 심사관마다 mid분에 몇 명을 심사할 수 있는지 카운트
        for time in times {
            cnt += mid / Int64(time)
        }
        
        // n명 이상 심사 가능할 경우 더 짧은 시간을 찾기 위해 right를 mid-1로 변경
        // n명 미만일 경우 가능한 시간을 찾기 위해 left를 mid+1로 변경
        if cnt >= n {
            res = mid
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    
    return res
}