[프로그래머스 43238 파이썬] 입국심사 (level 3, 이분 탐색)

알고리즘 유형 : 이분 탐색
풀이 참고 없이 스스로 풀었나요? : △

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

소스 코드(파이썬)

# mid분 동안 n명이 모두 심사를 받을 수 있는지 검사
def judge(mid, n, times):
    # 모든 심사대에서 mid분 동안 심사할 수 있는
    # 최대 인원을 모두 더함
    # 이 값이 n 이상이면 True 아니면 False
    if sum([mid // x for x in times]) >= n:
        return True
    
    return False

def solution(n, times):
    answer = 0
    times.sort()
    
    start, end = 1, times[-1]*n
    
    while start <= end:
        mid = (start + end) // 2
        result = judge(mid, n, times)
        
        # mid분 동안 모든 사람을 심사할 수 있다면,
        # mid보다 더 적은 시간동안 모든 사람을 심사할 수
        # 있는지를 알아봐야하므로 구간을 작은 쪽으로 좁혀주기
        if result:
            end = mid - 1
        else:
            start = mid + 1
    
    return start

풀이 요약

1. 탐색 대상을 "시간"으로 두고, 분할 기준을 "해당 시간동안 n명을 모두 심사할 수 있는지 여부"로 두고 이분 탐색을 실행해서 푼다.

2. 탐색 범위의 최댓값은 심사대에서 가장 오래 걸리는 심사 소요 시간 x n 이다.

3. mid분 동안 n명이 모두 심사를 받을 수 있는지 판단하는 방법은, 모든 심사대(times)를 순회하면서, 각 심사대에서 mid분 동안 심사할 수 있는 최대 인원 수를 모두 더해준다. 이 값이 n 이상이면 mid분 동안 n명을 모두 심사할 수 있다는 뜻이다.

배운 점, 어려웠던 점

• 오랜만에 이분 탐색 문제를 접해서 전혀 감도 못잡고 있었는데, 이전에 푼 이분 탐색 문제들을 복기하고나니 풀이가 보였다. 날 잡고 복습을 쫙 돌려야겠다.