입국심사

문제

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

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

---

풀이

처음엔 이분탐색을 사용하지 않고 time stamp를 찍어 반복문을 돌 때마다 시간이 1씩 경과하도록 구현하였다. 그런데 역시나 시간초과에 걸렸다. 어려웠던 부분이 어떠한 기준으로 이분탐색을 하고, 어떤 값을 탐색으로 찾아야 하는지를 정하는 것이었다. 결국 다른 블로그를 참고해서 구현하였다.

먼저 이분 탐색으로 찾아야 하는 값은 "return해야 하는 최소 소요 시간"이다. 그리고 탐색의 기준은 해당 시간만큼 주어졌을 때 검사관들이 모든 사람들을 검사할 수 있는지의 여부이다.

만약 모든 심사관이 주어진 시간 동안 검사한 인원 수가 n보다 작다면 시간을 더 주어야 하므로 left = mid+1을 해준다. 반면, 인원 수가 n보다 크면 일단 모두 검사받을 수 있는 것이므로 right = mid-1을 해서 시간을 줄여본다.

이 문제에서 이분 탐색이라는 알고리즘을 사용할 수 있는 이유는 다음과 같다.

• return 해야 하는 값인 시간의 범위가 정해져있다. -> 1~max(times)*n + 시간은 어차피 정수값으로 나와야 함
• 고로, 탐색을 통해 범위 안에서 최적의 값을 찾아내면 된다.
• 이 때, 이분탐색을 쓰면 선형탐색보다 시간을 줄일 수 있다.

def solution(n, times):
    left, right = 1, max(times)*n
    while left <= right:
        people = 0
        mid = (left+right)//2   # mid는 심사관에게 주어진 시간
        for i in range(len(times)):
            people += mid//times[i]
        if people >= n:
            answer = mid
            right = mid-1
        else:
            left = mid+1
        
    return answer

 

출처

• post.naver.com/viewer/postView.nhn?volumeNo=27248090&memberNo=33264526