[프로그래머스] 입국 심사

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/43238

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

 

이분 탐색을 연습하기 위해 고른 문제인데...

처음에는 '이 문제를 어떻게 이분 탐색으로 해결할 수 있지?' 하고 고민했던 문제입니다.

 

그래서 약간의 힌트를 참고했는데...

맨 처음에 최소시간 0을 left, 최대 소요 시간을 right로 둡니다. 이때 최대 소요 시간은 (사람 수 n * 가장 오래 걸리는 심사관의 시간)이 됩니다.

mid = (left + right) / 2가 되지요.

 

다음으로, 모든 검사관들의 소요 시간에 대해,

mid를 각 소요 시간으로 나눈 값을 총 소요 시간 total_times에 누적시킵니다.

이 값이 n보다 작다면 left = mid + 1로 해주고, 그렇지 않다면 right = mid - 1, answer = mid 의 형식으로 갱신해 나갑니다.

이 루프는 left > right가 되면 종료합니다.

 

맨 마지막에 얻게 되는 answer 값이 정답이 됩니다.

 

채점 결과

이분 탐색 문제는... 알고리즘 자체에 대한 이해도 중요하지만

실제 문제를 어떻게 이분 탐색의 형태로 모델링할 수 있는지 여부가 더 중요한 것 같습니다.

사실 모든 문제가 그렇겠지만...

 

아무튼 풀었으니 기쁘네요 ㅎㅎ