[이분탐색] 프로그래머스 Lv3. 입국심사 - Python

🗂️ 문제

링크: https://school.programmers.co.kr/learn/courses/30/lessons/43238?language=python3#

프로그래머스

 

💡 접근법

문제에서 원하는 것은 모든 사람이 심사를 받는데 걸리는 시간이므로 start와 end 그리고 mid 모두 시간에 관련된 변수라고 짐작할 수 있다. 즉, 입국 심사에 걸리는 최소 시간과 최대 시간을 의미하므로 low는 1로 지정하고 high는 max(times) * n로 지정한다.

 

탐색할 범위를 지정했으므로 mid 값을 변경시켜 값을 확인해야 한다.

mid를 통해 각 심사위원이 mid 시간 동안 몇명의 사람을 심사할 수 있는지 확인한다.

 

심사 가능한 사람의 수가 n보다 작으면 mid 값을 키워야 하므로 low=mid+1로 설정한다.

반대의 경우는 mid값을 줄여야 하므로 high=mid-1로 설정한다.

이때 심사에 걸리는 최소 시간을 구하는 것이 목표이므로 최솟값을 구하기 위해 mid값을 계속해서 줄여야 한다.

 

최종적으로 low값이 심사에 걸리는 최소 시간이 된다.

 

😎 내 코드

def solution(n, times):
    low = 1  # 심사에 걸리는 최소 시간
    high = max(times) * n  # 심사에 걸리는 최대 시간
    while (low <= high):
        mid = (low+high) // 2
        
        cnt = 0
        for time in times:
            cnt += mid // time  # mid 시간 동안 몇명의 사람을 심사 가능한지 확인
        
        if cnt >= n:
            high = mid - 1
        elif cnt < n:
            low = mid + 1

    return low

 

🧐 배운 점

• high 값을 10억으로 설정했을 때 mid를 계산하는 과정을 출력하여 확인해보니 계산이 제대로 되지 않았다. 너무 큰 값으로 설정해서 그런 것 같다.