[PROGRAMMERS] 이분 탐색 : 입국심사Python

이 문제를 처음 본 순간 든 생각은 이게 왜 '이분 탐색'이지? 였다. 다른 방법으로 풀까 했지만 n이 1,000,000,000을 for 문으로 돌릴 자신이 없었기 때문에 결국 다른 풀이들을 레퍼런스 했다.

다른 블로그 글들을 보면서 내가 아직 이분 탐색을 제대로 이해하지못했고, 아직 많이 부족하다는 것을 깨달았다.

우선, 다른 풀이들을 보면서 나 스스로 한번 문제와 이분탐색을 정리해보았다.

1.  이진 탐색은 정렬된 배열에서 내가 원하는 값을 가지고 있는 배열의 인덱스를 찾는 기법이다
2.  즉, 이문제에서 우리가 찾고 싶은 것은 총 소요되는 최소 시간이기 때문에 시간을 인덱스로 생각해야 한다.
3. 시간을 인덱스라고 생각하고 이분 탐색하듯이 LEFT와 RIGHT값을 찾아야 하는데, 시간은 무한하기 때문에 우리가 범위를 결정해야 할 필요가 있다. ( 범위 자체는 답만 포함하기 때문에 큰 의미는 없을 것 같지만 나는 이해를 위해 최대한 논리적 일관성을 맞춰보았다.)
   
   • RIGHT(최댓값) 현 문제 상황에서 걸리는 최대 시간 (N명 * 가장 느림 심사원이 걸리는 시간)
   • LEFT(최솟값) 아무도 심사해주지 않는 경우 ( 0)
4. 이렇게 최소, 최댓값을 설정해 둔 후, MIDDLE (시간) 값을 찾아서 이 시간이 있으면 n명의 사람들 모두 검사가 가능한지 확인한다.
5. 시간이 부족하면 LEFT값을 MIDDLE + 1로 바꿔주고, 시간이 남는다면 RIGHT  값을 MIDDLE - 1로 바꿔준다.
6. 여기서 조심할 점은 기존의 이분 탐색은 미들값이 우리가 찾는 값과 같다면 바로 반환을 하지만, 여기서는 최소의 시간을 찾기 때문에 원하는 미들값을 찾아도 시간이 남았을 때 하는 조정과정을 반복한다

이를 코드로 나타낸다면,

이분탐색 풀이과정

이렇게 된다.

이분탐색은 조금 기초에 영역이라고 생각했기 때문에, 이렇게 문제를 풀 수 있다는 것을 상상도 하지 못했다. 역시 세상에 불필요한 지식은 없는 것 같다.

탐색 문제를 이런 식으로 낼 수 있구나를 알려주는 좋은 문제였던 것 같다. 

문제 출처 : 프로그래머스 https://programmers.co.kr/learn/courses/30/lessons/43238