[프로그래머스 level3 입국심사] 이분 탐색 활용하기

해결해야하는 문제는 다음과 같았다.

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

코딩테스트 연습 - 입국심사

 

 

처음에 문제를 접하였을 때에는, 이분 탐색이라고 적혀있었지만 자연수의 분할이 떠올랐다.

입국장의 개수만큼 사람 수를 분할하여, 가장 큰 시간이 걸리는 입국장과, 가장 적은 시간이 걸리는 입국장의 차이가 가장 작다면, 그때가 가장 최단 시간이 걸리는 경우라고 생각하였다. 하지만 이는 생각이 매우 짧았던 것이었다.

from itertools import combinations_with_replacement
def DIVID(n,m):
    A=[list(x) for x in combinations_with_replacement(range(1,n),m) if sum(x)==n]
    return A
    
    
def solution(n, times):
    answer = 0
    num_divids = DIVID(n,len(times))
    
    dif_time = int(1e9)
    
    times.sort(reverse=True)
    
    for num_divid in num_divids :
        time_list = []
        for i in range(len(times)):
            time_list.append(times[i]*num_divid[i])

        if max(time_list) - min(time_list) < dif_time :
            dif_time = max(time_list) - min(time_list)
            answer = max(time_list)
            
    return answer

 

 

따라서 이분 탐색이라는 키워드에 맞게 어떤 방식으로 하는 것이 좋을지 아이패드에 계속 끄적여봤다.

 

 

 

def solution(n, times):
    answer = 0

    left = 1
    right = max(times) * n

    while left <= right:
        mid = (left + right) // 2
        count = 0
        for time in times:
            count += mid // time
            if count >= n: 
                answer = mid
                right = mid - 1
                break
        
        else :
            left = mid + 1

    return answer

 

이 문제는 

• 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
• 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
• 심사관은 1명 이상 100,000명 이하입니다.

조건이 굉장히 큰 수들이다.

효율적으로 코드를 작성해야 할때, 이분탐색 알고리즘이 많이 사용된다는 것을 알 수 있었다.