프로그래머스 - 입국심사 문제 풀이
: 레벨 체크 lv3에서 이 문제 때문에 통과를 못했다... 나머지 한문제는 제대로 기억은 안나는데 DB를 이용해서 푸는 문제였다(피보나치 유형). 아쉽지만 lv3은 다시 도전해보도록 하고! 오늘은 이 문제를 파헤쳐본다.
문제 해석
: 문제에서 요구하는 것은 주어진 심사관의 정보를 바탕으로 대기하는 사람의 수만큼을 심사를 본다면 모든 사람을 심사보는데에 걸리는 최소값은 몇시간인가이다.
문제 분석 및 해결책
: 처음에는 일단 빠르게 비는 심사관에게 기다리는 사람을 투입(?)시키고 마지막에 심사관보다 기다리는 사람의 수가 더 적을 때 효율적인(?) 방법을 써서 최소값을 만드나보다 생각했다. 일단 비는 심사관이 없는 방향으로 만드는 것이 최고로 효율적일 것이라고 생각했기 때문이다. 하지만, 만약에 한 심사관이 1만에 해결할 수 있고, 한 심사관은 10만에 해결할 수 있다면 1만에 해결할 수 있는 심사관을 여러번 굴리는 것(?)이 효율적이다. 즉, 1만에 해결할 수 있는 심사가 끝나기를 기다렸다가 그 사람한테 보내는게 낫지, 자리가 비었다해서 10만에 끝내는 심사관에게 보내면 비효율적이라는 것. 이렇게되면 문제를 어떻게 해결할 수 있을까??... 가 내 마지막 유..언(?)은 아니고 이문제를 못푼 나의 마지막 외침이었다.
이 문제의 포인트는 '심사를 끝마칠 수 있는 최소한의 시간'을 구하는 것이다. 그러기 위해서 완전탐색을 하기에는 주어진 인풋의 제한이 너무크다(10억). 그러면 특정 수(심사를 끝마칠 수 있는 최소한의 시간)를 구하기 위해 좀더 효율적인 알고리즘을 찾아내야한다. 이 때, 주먹구구식으로 넣어보는 방법은 여기서 통하지 않는다. 사실 여기서 '이분탐색'을 떠올리는 사람들의 머리는 어떻게 된건지 궁금한데.. 이분탐색을 떠올려야 풀 수 있는 문제이다. 약간 역발상이 필요한 부분 같은데, 기다리는 사람을 어떤 심사관에게 투입해볼까를 고민하는게 아니라 '심사를 끝마칠 수 있는 시간을 몇시간을 줘볼까'로 접근하는 것이다. 최대 시간을 줘보고, 그 시간만에 심사가 가능하면? 그 시간을 줄여본다. 그래도 가능하면? 또 줄여본다. 이렇게 줄이다보면 가능하지 않은 포인트가 있을 것인데, 그 경계가 되는 가능한 시간이 최소시간일 것이다. 그러면 사실 이것도 완전탐색처럼 시간이 많이 걸리게 되기에 이러한 탐색을 이분탐색으로 해서 효율화 시키는 것이다(logN).
다시 정리해보면, 최소한으로 걸리는 시간을 찾기 위해 1부터 최악의 케이스(가장 오래걸리는 시간) 사이의 시간을 주먹구구 식으로 줘보는 것이다(완전탐색). 그러면 언젠가 그 시간안에 주어진 사람수 만큼 심사를 볼 수 없는 포인트가 있을 것이다. 그러면 그 바로 직전에 심사를 볼 수 있었던 포인트가 정답이 될 것이다. 하지만, 이 방법은 시간복잡도에서 걸리기에 여기서 정렬된 상태에서 어떤 값을 찾을 때 가장 효율적인 알고리즘인 이분탐색을 쓰는 것이다.
** 여기서 이분탐색을 떠올리려면 문제를 많이 풀어보는 수밖에 없을 것 같다.
어쨌든 포인트는 최소 심사 시간을 구하라해서 나같은 경우에는 '구현'문제를 풀 때 처럼 실제 심사 과정을 시뮬레이팅해보려 했는데, 그러지 않고 심사 시간을 최악의 시간부터 차례로 주면서 최소값을 찾는 발상을 했다는 것과 거기서 이분탐색을 떠올린 것이다. 사실 더 중요했던건 최악의 시간부터 차례로 주면서 최소값을 찾는 발상인 것 같다.
내 코드
def solution(n, times):
maximum_time = max(times) * n
minimum_time = 1
answer = 0
while minimum_time <= maximum_time:
mid_time = (maximum_time + minimum_time) // 2
people_cnt = 0
for time in times:
people_cnt += mid_time // time
if people_cnt >= n :
maximum_time = mid_time - 1
answer = mid_time
elif people_cnt < n:
minimum_time = mid_time + 1
return answer
마무리
: 나중에 꼭 한번 더 풀어봐야겠다. 심사를 마칠 수 있는 최악의 시간부터 차례로 적용시키면서 심사관의 실력(심사에 걸리는 시간)을 바탕으로 해당 시간이 주어지면, 기다리는 사람 수를 감당할 수 있는지를 체크하고, 감당할 수 있으면 주는 시간을 더 줄여보고, 감당할 수 없으면 주는 시간을 늘려봄으로써 그 경계(감당과 감당불가)를 찾는 발상...!
