Level 3 입국심사 Python 3

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

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

 

최종 코드

• GitHub https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level3_입국심사.py

hwayeon351/Programmers-Algorithms

def solution(n, times):
    answer = 0
    left = 1
    right = min(times)*n
    while left <= right:
        mid = (left+right)//2
        cnt = 0
        for t in times:
            cnt += mid//t
            if cnt >= n:
                answer = mid
                right = mid-1
                break
        if cnt < n:
            left = mid+1           
    return answer

---

풀이 과정

특정 시간에 심사대에서 최대한 많이 심사할 수 있는 사람 수는 시간//심사 소요 시간이다.

특정 시간에 심사를 모두 할 수 있는지 아닌지의 여부를 파악하여 최소 시간으로 모든 사람을 심사할 수 있는 시간이 언제인지 찾아나가는 이진 탐색 알고리즘을 적용했다.

이진 탐색은 left와 right 값을 조정하여 탐색 범위를 좁혀 나가면서 (left+right)//2인 mid 값이 target이라면 return 하는 탐색 알고리즘이다.

만약 8개의 데이터 중에서 target을 찾는데 소요되는 시간은 최악의 경우 8, 4, 2, 1개의 데이터들을 1회씩 탐색하므로 4가 된다.  

탐색을 진행하면서 데이터의 개수가 n이 1이 될 때까지 1/2개씩 계속해서 작아지기 때문에 n * (1/2)^k = n * 2^(-k) = 1 이며, 즉, n = 2^k가 된다. 따라서, 이진 탐색의 시간 복잡도는 O(log2 n)이 된다.

def solution(n, times):
    answer = 0
    #최소 1분이 걸림
    left = 1
    #심사 시간이 가장 적게 걸리는 심사대만 이용하는 경우가 정답이 될 수 있는 가장 최대의 시간
    right = min(times)*n
    
    #left가 right보다 클 때 종료
    while left <= right:
    	#탐색하고자 하는 시간
        mid = (left+right)//2
        #cnt = 심사 가능한 사람 수
        cnt = 0
        for t in times:
        	#각 심사대에서 mid까지의 시간동안 심사할 수 있는 사람 수 카운팅
            cnt += mid//t
            #mid까지의 시간 동안 심사 가능 인원이 n명 이상인 경우
            if cnt >= n:
          		#mid를 answer로 갱신
                answer = mid
                #더 적은 시간에서도 모든 인원을 심사할 수 있는지를 탐색하기 위해 right를 mid보다 1 적게 설정
                right = mid-1
                break                
        #mid까지의 시간 동안 n명을 모두 심사 할 수 없는 경우
        if cnt < n:
        	#더 많은 시간에서의 탐색이 필요하므로 left를 mid보다 1 크게 설정
            left = mid+1           
    return answer
    #시간복잡도 = O(log2 n), 공간복잡도 = O(n)