[파이썬/알고리즘] 프로그래머스 - 입국심사 (이분 탐색)

[문제]

n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.

처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.

모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.

입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.

제한사항
입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
심사관은 1명 이상 100,000명 이하입니다.

 

[풀이]

def solution(n, times):
    left = 1
    right = max(times) * n
    
    while left <= right:
        mid = (left+right)//2
        people = 0
        
        for time in times:
            people += mid//time
            
            if people >= n:
                break
        if people >= n:
            answer = mid
            right = mid - 1
        else:
            left = mid + 1
    return answer

 

이분 탐색 문제이다.

input 값이 엄청 클 때는 이분탐색을 떠올려야 한다.

 

left = 1

right = max(times) * n

최솟값과 최댓값을 left, right로 선언해준다.

여기서 최솟값인 left는 1분을 의미하고, right는 심사를 하는데 가장 오래 걸리는 심사관이 모든 사람을 심사하는데 걸리는 시간이다. 즉, 최솟값에서 최댓값으로 범위를 설정해주는 것이다.

 

만약 n이 4이고  times가 [2,5] 라면 1분에서부터 최대 20분까지 걸리게 된다.

 

처음에는 left를 1 * n을 주려고 했는데, 그렇게 되면 한 명의 심사관이 하는 경우와 동일하다.

즉 n이 4이고 한 명의 심사관이 1분 걸린다면 4분이 되지만 2명의 심사관이 1분씩 걸린다면 2분으로 끝난다.

그렇기 때문에 left는 1분부터 주는 것이 더 타당하다.

 

 

while left <= right:
     mid = (left+right)//2
      people = 0

최솟값이 최댓값이랑 동일하거나 작아질 때까지 반복하게 된다.

 

mid는 현재 심사의 중간값을 의미한다.

이분 탐색을 할 때는 최솟값에서부터 탐색하는 것과 최댓값에서부터 탐색하는 것이 나뉘어지기 때문에 중간값을 계산해줘야 한다.

 

people은 mid의 시간동안 심사할 수 있는 총 사람의 수를 저장하는 것으로 초기화 해준다.

나중에 심사를 받으러 오는 사람의 수(n) 이랑 비교하게 된다.

 

위 예제로 들면 여기서 mid 값은 left = 1, right = 20이므로 21 // 2 = 10이 된다.

 

 

for time in times:
     people += mid//time

시간동안에 얼마나 심사할 수 있는지를 계산해줘서 people에 넣어준다.

위 예제를 그대로 넣으면 mid는 10이고 time은 [2,5] 이면 10//2 = 5가 people에 넣어지고 10//5=2가 people에 누적으로 합해진다. 따라서 여기서 people은 7이 되는 것이 맞지만 아래 if문에 의해서 5에서 빠져나간다.

 

if people >= n:
      break

people이 5가 되었을 때 n인 4보다 크므로 멈추고 해당 반복문을 나가게 된다.

 

if people >= n:
       answer = mid
       right = mid - 1

for 반복문을 빠져나가고, 위에서 people이 n보다 컸기 때문에 여기서 값을 다시 찾게 된다.

 

위에서 구했던 mid = 10분이라는 값을 정답값에 입력하고 오른쪽 값을 줄이게 된다.

그럼 right는 처음에 20이었던 값이 9로 줄여지게 되고 다시 left 값인 1분부터 right 값 9분까지를 탐색하게 된다.

 

여기서 다시 while문을 반복해서 다시 계산을 하게 되면 mid = (1 + 9)/2 를 해서 mid는 5가 된다.

다음 for문을 돌게 되면,  people += 5 / [2, 5]가 되면 5/2= 2, 5/5=1 해서 2+1 = 3이 된다. 

그럼 n은 4명인데 people은 3 이므로 한 명이 부족하게 된다.

 

else:
      left = mid + 1

for 반복문이 끝나고,  if문 둘 다 조건에 걸리지 않기 때문에 else문으로 들어가서 left에 mid +1 을 해준다. 

mid는 위에서 5였기 때문에 5+1은 6하면 left가 6이 된다.

 

그리고 다시 위에 while문을 돌게 되면서 mid = (6+9)/2 하면 7.5 이지만, 소수점을 버리고 7이 된다.

 

mid = 7에서 다시 위 반복문을 실행하게 된다.

그러면 최종적으로 6이 나오게 된다.