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

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

프로그래머스

---

이분탐색 카테고리에 있는 문제였지만, 이분탐색으로 푸는 방법을 찾기까지 시간이 좀 걸렸다.

'시간의 최소값'에 집중하면, 어떤 순서로 검사받든 가장 최소로 걸리는 시간을 계산하면 되는데, 

심사받는 순서에 집중을 하다보니 이분탐색 풀이법이 바로 떠오르지 않았다.

 

def solution(n, times):
    min_val = 1
    max_val = max(times)*n
    answer = 0
    
    while min_val <= max_val:
        mid_val = (min_val+max_val)//2
        ans = 0
        for time in times:
            ans += mid_val//time
        if ans >= n:
            answer = mid_val
            max_val = mid_val-1
        elif ans < n:
            min_val = mid_val+1
            
    return answer

위 코드로 문제를 해결했다.

먼저 min_val은 문제 조건에 의해 1을 줘도 되고(한명을 검사하는 최소 시간이 1분이고, 입국 심사를 기다리는 사람은 1명 이상이기 때문),

min(times) 값을 줘도 된다. (times 배열의 최소 시간만큼은 걸리기 때문)

max_val은 최대로 걸릴 수 있는 시간 (times 배열의 최대 시간*사람 수)을 지정한다.

 

min_val이 max_val 보다 작거나 같을 동안 mid_val이 최대 몇명을 수용하는 시간인지 계산한다.

예를 들어 min_val이 1이고 max_val이 60이라고 하자. (문제 예시)

이때 mid_val==20이 된다. 20분의 시간동안 검사받을 수 있는 사람 수(ans)는 7분 2명, 10분 2명으로 총 4명이다.

이는 사람 수인 n값 보다 작으므로 min_val의 값을 mid_val+1로 바꿔서 다시 계산한다.

 

이러한 과정을 min_val <= max_val인 동안 반복한다.

 

이때 검사 받을 수 있는 사람 수인 ans 값이 n보다 크거나 같을 때, answer 값을 갱신한다.

처음에는 이 부분이 헷갈려서 아래와 같이 작성했다.

        if ans > n:
            max_val = mid_val-1
        elif ans <= n:
            min_val = mid_val+1
            answer = mid_val

그런데 이렇게 풀면 완전 오답이다.

왜냐하면 검사 받을 수 있는 사람 수가 실제 사람 수보다 작거나 같을 때 answer값을 갱신하기 때문이다.

 

검사 받을 수 있는 사람 수가 실제 사람 수 보다 많거나 같아야 현재의 mid_val 시간으로 커버가 가능하다는 의미가 성립한다.

 

이분탐색 문제를 풀 때 범위 지정에 유의해야할 것 같다.