[프로그래머스] 입국심사 - 파이썬(python)

 

 

 

나의 풀이

def binarySearch(left, right, n, times):
    
    answer = right 
    
    while left <= right :
        mid = (left+right) // 2
        cnt = 0
        for t in times :
            cnt += mid // t
        if cnt >= n :
            answer = min(answer, mid);
            right = mid - 1
        else :
            left = mid + 1
        
    return answer

def solution(n, times):
    
    min_time = 0
    max_time = max(times) * n

    answer = binarySearch(min_time, max_time, n, times)
    
    return answer

• 이분탐색은 탐색하는데 걸리는 시간이 O(log N) 이기 때문에, 탐색해야 하는 input 이 아주 큰 숫자일 때 사용하기 좋다.
• 따라서, 위 문제에서도 심사를 하는데 걸리는 시간을 기준으로 이분탐색 (1분 ~ 심사하는데 최대로 걸리는 심사위원의 시간 * N) 을 진행하였다.
• 시간을 조절하면서, 만약 해당 시간안에 N이라는 사람을 모두 심사할 수 있다면, answer 과 비교하여 더 작은 수라면 최소시간으로 갱신한다. 

 

• mid = ( left + right ) // 2 라는 중간 시간을 정한 다음, mid 시간 안에 처리할 수 있는 사람의 수를 계산한다.
  • for t in times :
            cnt += mid // t
• 이때 심사할 수 있는 사람 수(cnt) 가 심사해야되는 사람수(N) 보다 많으면 최소 시간을 잡기 위해 시간을 줄여본다. 
  •            answer = min(answer, mid);
                right = mid - 1
• 만약, 심사할 수 있는 사람 수(cnt) 가 심사해야되는 사람수(N) 보다 적으면 시간을 늘여야 한다.  
  •             left = mid + 1