[프로그래머스] 파이썬 _ 입국심사

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

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

 

문제유형 : 이진탐색

 

문제풀이 : 

 

• 이문제는 파라메트릭 서치 이며 파라메트릭 서치 문제는 일반적으로 이진탐색을 통해 해결할 수 있다.
  • 파라메트릭 서치 : 최적화 문제를 결정문제로 바꾸어 해결하는 기법으로, 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제이다.

• 이분탐색에서, 탐색범위를 조정하는 기준이 되는것으로 이 문제에서는 모든 사람이 입국심사를 완료하는 시점을 택한다.
  • 현재 종료시점이 여기일때 모든 사람이 입국심사를 완료할 수 있나? -> 조건의 만족여부(예, 아니오) 에 따라서 탐색범위를 조정한다.

• 이진탐색의 탐색범위 : 시작은 0으로 설정하고 끝점은 최ㅣㅣㅣ대는 int(1e18)인데 너무 크기때문에 times에서 가장 오래걸리는 시간에 *n을 하는것으로 끝점을 설정한다.

한마디 :

• 처음에 그냥 완전탐색(그리디느낌)으로 풀어서 시간초과가남 
  • 모든 심사원들에 대해서 현재 어떤 사람이 각 심사원들을 선택했을때의 최종시간을 모두 비교해서 가장 짧은것을 택하는 식으로 했는데 범위가 10억이라 당연히 시간초과가 날것같긴했는데 일단 풀어봄 ㅋㅅㅋ  답은 나오지만 효율성 똥망
• 문제에서 탐색범위가 10억단위처럼 매우 클때는 꼭 이진탐색을 떠올리자.

 

정답코드 :

def solution(n, times):
    
    start = 1
    end = max(times)*n
    
    result = end
    
    while start <= end:
        cnt = 0
        mid = (start+end)//2
        
        for i in times:
            cnt += mid//i
            
        if cnt >= n:
            result = mid
            end = mid-1
        else:
            start = mid+1            
    
    return result