프로그래머스. 입국심사

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

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

 

카테고리가 이분탐색으로 되있었는데 처음에는 그냥 n의 최댓값 상관안하고 마음대로 풀었더니 당연히 시간초과가 났다.

이분탐색이라길래 나는 c++의 upper_bound나 lower_bound를 활용하는 문제인줄 알고 

시간을 일일히 구하는데 구할때 해당 함수를 써서 풀었더니 틀렸다고 나왔다.

 

코드를 계속 바꿔봤는데 결국 안풀려서 다른 분들 코드를 봤는데 다음과 같이 푸는 문제였다.

이분탐색에서 

left = 심사걸리는 최소 시간, 즉 0

right = 최대 시간, 즉 주어진 times중 최댓값 *  n 

이 상태에서 mid를 구해서 이분탐색을 진행하는 문제였다.

 

n = 6, times[] = {7, 10} 라면 

left = 0, right = 60, mid = 30 

30분일때는 30/7=4 + 30/10=3 = 7명 심사가능.

n=6이므로 right = mid - 1

 

left = 0, right = 29, mid = 14

14분일때는 14/7=2 + 14/10=1 = 3명 심사가능.

left = mid + 1 

 

left = 15, right = 29, mid = 22 

22분일때는 22/7=3 + 22/10=2 = 5명 심사가능 

left = mid + 1

 

left = 23, right = 29, mid = 26

26분일때는 26/7=3 + 26/10=2 = 5명 심사가능 

left = mid + 1

 

left = 27, right = 29, mid = 28

28분일때는 28/7=4 + 28/10=2 = 6명 심사가능 

 

right = 27, left = 27 : left <= right == false므로 탈출