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

프로그래머쓱

해당 글에서는 입국심사 문제를 Python을 이용해 풀이하고자 한다.

프로그래머스

 

🔷 문제 설명

이 문제는 이분탐색에 관련된 문제다.

코딩테스트를 보기에 앞서 평소에 이분탐색 문제인 것을 알아내는데 어려움을 느껴 연습하는 시간을 가지고자 해당 문제를 풀게 됐다.

 

🔷 문제 풀이

만약 이 문제가 이분탐색인 문제라는 걸 몰랐다면 어떻게 접근했어야 할까?

이분탐색이라는 것의 힌트는 바로 입력의 크기이다. 해당 문제에서 입국심사를 기다리는 사람의 최댓값과 한 명을 심사하는데 걸리는 최대 시간은 1,000,000,000이다. 따라서 O(log n) 혹은 O(1)로 풀어야 하는 문제이다.

 

따라서 O(log n)에 대표적인 알고리즘인 이분 탐색(Binary Search)을 떠올릴 수 있는 것이다.

혹시나 해당 문제가 잘 이해가 되지 않는다면, 백준 16401 - 과자 나눠주기 문제를 먼저 풀어보는 것을 추천한다.

 

1️⃣ Python 풀이

이 문제에서 찾아야 하는 값은 모든 사람이 심사는 받는데 걸리는 시간의 최솟값이다. 아래 코드에서는 result가 이에 해당한다.

 

만약 입력의 크기가 작았다면 1부터 1씩 증가시키며 모든 사람이 심사를 받을 수 있는 최댓값을 구하면 됐겠지만, 해당 문제에서는 입력이 매우 큰 값이므로 시간 초과가 발생할 것이다. 따라서 모든 사람이 심사를 받을 수 있는 시간의 최솟값인 result를 이분 탐색을 통해 찾을 것이다.

 

[이분탐색 코드]

아래는 이분탐색 코드를 해당 문제에 맞게 구현한 코드이다. 코드의 핵심은 다음과 같다.

• 심사 받는데 끝나는 시간인 mid에 따라 각 심사대에서 몇 명이나 심사를 받을 수 있는지를 나타내는 num을 계산한다.
• 현재 mid값에 대해 심사할 수 있는 사람의 수인 num과 문제에서 제시한 n(입국심사를 기다리는 사람 수)를 비교한다.
  • num < n인 경우
    • 이는 기존에 입국심사를 해야 하는 사람(n) 보다 적게 한 경우이다. 즉, 현재 심사 시간이 부족하다는 뜻이다.
      따라서 현재 심사 시간을 나타내는 mid를 증가시켜야 한다. (start = mid + 1)
  • num >= n인 경우
    • 이는 입국심사를 해야 하는 사람을 모두 확인할 수 있는 경우다. 하지만 시간을 더 줄일 여지가 있을 수 있다.
      따라서 현재 심사 시간을 나타내는 mid를 감소시키면서 n명을 심사할 수 있는 가장 작은 mid값을 찾아야 한다.
    • 해당 조건문에 마지막에 들어온 값이 모든 사람이 심사를 받는데 걸리는 시간의 최솟값이 되므로, 따로 result 변수에 저장했다.

def binary_search(start, end, times, n):
    while start <= end:
        mid = (start+end)//2 # 모든 사람이 심사를 받는데 걸리는 시간
        num = 0 # 탐색 받은 사람의 수
        for t in times:
            num += mid // t
        if num < n : # 기존 사람보다 적게 확인한 경우
            start = mid + 1 # 시간을 늘려야 함.
        else: # 기존 사람보다 많이 확인한 경우
            end = mid - 1 # 시간을 줄여야 함.
            result = mid
    
    return result

 

[solution 함수]

아래 코드의 핵심은, binary_search 함수의 argument를 어떻게 넣어주냐이다.

해당 문제에서는 n의 범위는 1부터 1,000,000,000이고, 검사 시간(times의 원소)의 범위는 1부터 1,000,000,000이다.

 

따라서 start는 1로, end는 times의 max값을 n번 곱한 값(n명이 모두 가장 긴 심사대에 가는 경우)이 될 수 있다.

def solution(n, times):
    max_time = max(times) * n
    answer = binary_search(1, max_time, times, n)
    return answer

 

[전체 코드]

def solution(n, times):
    max_time = max(times) * n
    answer = binary_search(1, max_time, times, n)
    return answer

def binary_search(start, end, times, n):
    while start <= end:
        mid = (start+end)//2 # 모든 사람이 심사를 받는데 걸리는 시간
        num = 0 # 탐색 받은 사람의 수
        for t in times:
            num += mid // t
        if num < n : # 기존 사람보다 적게 확인한 경우
            start = mid + 1 # 시간을 늘려야 함.
        else: # 기존 사람보다 많이 확인한 경우
            end = mid - 1 # 시간을 줄여야 함.
            result = mid
    
    return result