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

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

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

문제풀이

어떤 것을 놓고 이분탐색을 해야할지 감이 안잡혔던 문제이다. 이분탐색을 생각하지 않고 접근해보았는데 시간초과가 났다..(이분 탐색을 써야 시간초과가 안나는 것 같다^^;)

1. 시간 배열에 주어진 시간 * 입국 심사 받을 사람들 이렇게 곱해서 가능한 시간들을 배열에 삽입한다

2. 정렬해서 6번째 시간을 출력한다.

 

최소시간 1분과 최대시간 사이에 이분탐색을 해서 총 n명이 입국심사를 받을 수 있으면 된다 !

 

알게 된 점

1. 최소 값을 찾아야하는 것이기 때문에 target number를 찾아도 왼쪽 구간을 더 탐색해서 최소값을 찾아야한다.

if tmp >= n:
	end = mid

2.  그냥 mid를 답으로 하면 start와 end가 같아졌을 때 start 값이 나오지 않고 1이 출력된다

if tmp >= n:
	end = mid
		if answer > mid:
			answer = mid

 

소스코드

def solution(n, times):
    start = 1
    end = max(times)*n
    answer = end
    while start < end:
        mid = (start + end)//2
        tmp=0
        for i in times:
            tmp += (mid//i)
        if tmp >= n:
            end = mid
            if answer > mid:
                answer = mid
        elif tmp < n :
            start = mid + 1
    return answer