프로그래머스 - 입국심사
https://programmers.co.kr/learn/courses/30/lessons/43238
처음에 이분탐색 말고 dfs완탐을 진행하니 시간초과가 발생했다.. 당연했다. n이 1,000,000,000이하로 주어지기에 dfs로 할 경우 n이 1,000,000,000인 경우 2^1,000,000,000 만큼 돌기 때문에 시간초과가 발생한다.. 다른 접근 방식을 찾지못해 설명을 봤다. 이분탐색으로 접근하는데 신기하다.. 왜 이 방식을 생각 못했을까.. 이분탐색으로 접근하면 어떤 값을 기준으로 범위를 좁혀 나가면서 답을 도출해야한다. 이 문제에서 기준은 시간이다. 이유는 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 요구함으로 시간을 기준으로 잡는다.
이 후 두 부분으로 나누는데 시간 기준으로 left는 가장 최솟값, right는 가장 최대값으로 잡아준다. left는 1이되고(n=1, 심사 시간 1), right는 (가장 오래걸리는 심사 시간)*n이 된다.
중간 값(left+right/2)을 총 소요된 심사 시간으로 설정하고 해당 시간에 몇명의 사람이 심사를 받을 있는지 확인하면된다. 만약 심사 가능한 인원이 n보다 작을 경우 전부 심사할 수 없으므로 탈락이다. 최솟값을 mid+1로 변경해준다. 만약 n보다 크거나 같다면 모두 심사 가능 함으로 최소 시간이 될 수 있으므로 answer을 변경해 준다. 이후 최대값(right)를 mid -1로 갱신해 주면 답을 도출 할 수 있다.
코드
def solution(n, times):
##시간으로 기준을 두었을 때 최소값을 초기값으로 설정
##n이 1이고, 심사 시간이 1분만 걸리는 심사관
answer = 0
left = 1
#times가 정렬되어있어야 한다.
#right는 최악의 시나리오 -> N명이 가장 오래걸리는 심사관에게 심사 받을 경우로 초기값을 설정
right = max(times) * n
while left <= right:
#총 소요 시간
mid = (left+right) //2
#심사받을 수 있는 사람 수
people_cnt =0
for time in times:
# mid시간 동안 심사 받을수 있는 사람 수
people_cnt += mid//time
#심사 받을수있는 사람의 수가 주어진 N보다 작으면 전부 심사받을 수 없으므로 최소시간을 갱신해준다.
if people_cnt <n:
left = mid+1
continue
#구한 만약 총 소요 시간이 현재 설정한 최악의 경우보다 작으면 최악의 경우를 갱신
if mid <= right:
answer = mid
right = mid -1
return answer