23.03.09 파이썬 코딩 퀴즈#191 입국심사(프로그래머스 스쿨)

이번 문제는 입국심사 문제이다.

n 명의 사람이 입국심사를 위해 줄을 서서 기다리고 있고, 각 입국심사대에는 심사관마다 검사하는데 걸리는 시간이 담긴 배열 times 가 존재한다. 이 때 n명의 사람을 검사하는데 소요되는 최소시간을 return 해야 한다.

입출력 예를 통해 살펴보면, 처음 시작은 비어있기 때문에 동시에 두 명의 사람이 심사를 받는다

7분이 되었을때 첫번째 심사대가 비고 3번째 사람, 10분이 되었을때 두번째 심사대에서 네번째 사람 순서로 계속 진행하게 된다.

20분이 되었을때, 두 번째 심사대가 비지만 이곳에서 6번째 심사를 받으면 총 30분이 소요된다.

따라서 1분을 더 기다렸다가(21분째) 첫번째 심사대에서 심사를 받으면 총 소요시간은 28분이 된다.

즉, 마지막 사람의 심사가 끝나는 시간을 return 하면 된다.

얼마전 풀었던 선입선출 문제와 비슷하다. 하지만 이 경우에는 딱히 순서를 지킬 필요가 없고, 끝나는 시간 기점으로 계산을 하면 되기 때문에 코드는 굉장히 간단하다.

maxtime 을 계산할때에는 max() 또는 그냥 times 의 아무 값이나 사용해도 무방하다. 그 이유는 어짜피 다른 심사대에서 동시에 검사를 하기 때문에 어느 값을 사용해도 return 해야하는 최소 시간을 초과하기 때문이다.

이제 반복문을 통해 start 와 maxtime 값을 증감 시켜 주면서 코드를 돌게된다.

만약 목표 n 보다 심사를 더 많이 할 수 있다면 maxtime을 mid 로 , 부족하다면 start 를 mid+1로 바꿔준 후 마지막 사람의 심사 완료 시간을 찾게 된다.

이러한 시간탐색 문제에는, 시작시간, 끝나는시간, 중간시간 총 3가지의 변수가 필요하다는 사실을 꼭 기억해야 한다.