[python3] 프로그래머스 입국심사 풀이 ( 이분 탐색 )

이거 어려웠다. 처음에 점화식을 세워야하나 많이 당황했다. 솔직히 이분탐색 문제가 아니었다고 한다면 제한된 시간내에 풀지 못했을거 같다.

일단 문제를 보자

 

문제를 읽어보면 입국심사가 필요한 인원과, 입국심사에 걸리는 시간이 존재한다. 이때 입국심사를 모두 마치기 위한 최소시간을 구하면 된다.

처음에는 이분탐색을 어디에 적용해야할지 몰라서 당황했다. 이후에 문제를 차분히 살펴보니 return값을 살펴보는게 어떨까라는 생각이 들었다.
정리된 생각은 아래와 같다.

1. 입국심사에 적은 시간이 걸리는 심사관이 많은 입국자를 받아야 총 시간이 줄어든다.
2. 최소시간을 times로 나누었을때 값을 더하면 n이 된다.

처음에는 1번에 꽂혀서 무조건 작은 시간을 많이 주고 하나씩 줄여가며 연산을 하면 되겠지라는 생각을 했다. 그러나 중요한것은 2번 이었다. 1번은 코드를 무작위로 대입하기 애매하고 구현하기도 애매하다.
그러나 2번은 최소시간을 기준으로 times들을 나누어보고 몫을 더하면 n보다 큰지 작은지 판단이 가능하다. 즉, 이분탐색으로 구하는게 가능해진다. 따라서 이를 토대로 구현하면 아주 쉽게 구현된다.

def solution(n, times):
    # 성립해야할 규칙은 sortd된수
    # 우선 sorted
    times = sorted(times)
    L = 1
    R = times[-1]*n
    final = 0
    while R >= L:
        M = int((L+R)/2)
        tmp = 0
        for div in times:
            tmp += int(M / div)
        print(tmp, L,M,R)
        if tmp >= n: # 일단 성립하니 저장하고 낮은거 찾으러간다.
            final = M
            R = M-1
        else: # 안되니까 L을 이동
            L = M+1
    return final

 

결론 : 이분탐색 어렵다.... 아직 L,R을 어떻게 설정해야하는지 기준을 명확하게 모르겠다.