[프로그래머스 / 이분탐색/ Python] 입국심사

문제 설명

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

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

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

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

제한사항

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

 

 

입출력 예 설명

가장 첫 두 사람은 바로 심사를 받으러 갑니다.

*7분이 되었을 때, 첫 번째 심사대가 비고 3번째 사람이 심사를 받습니다.

*10분이 되었을 때, 두 번째 심사대가 비고 4번째 사람이 심사를 받습니다.

*14분이 되었을 때, 첫 번째 심사대가 비고 5번째 사람이 심사를 받습니다.

*20분이 되었을 때, 두 번째 심사대가 비지만 6번째 사람이 그곳에서 심사를 받지 않고 1분을 더 기다린 후에 첫 번째 심사대에서 심사를 받으면 28분에 모든 사람의 심사가 끝납니다.

---

풀이 코드 

 

def solution(n, times):
    
    times.sort()
    min_time = 0
    max_time = times[-1] * n

    
    while min_time <= max_time:
        count = 0
        mid_time = (min_time + max_time) // 2
        
        for time in times:
            count +=  mid_time // time
            
            if count > n:
                break
        
        if count >= n:
            max_time = mid_time - 1
            answer = mid_time
        
        elif count < n:
            min_time = mid_time + 1
        
    return answer

 

---

풀이 과정

 

input이 최대 10억개이므로 logN을 이용한 알고리즘을 쓰지 않으면 시간초과가 날 수 밖에 없는 문제이기에,  문제 주제인 '이분탐색'을 이용해 문제를 풀려고 노력했다. 이분탐색의 대표적인 알고리즘 코드를 보면

 

def binary_search(target, data):
    data.sort()
    start = 0
    end = len(data) - 1

    while start <= end:
        mid = (start + end) // 2

        if data[mid] == target:
            return mid
        elif data[mid] < target:
            start = mid + 1
        else:
            end = mid -1

 

이다. while문의 조건으로 시작 지점이 끝 지점보다 크면 루프를 빠져나오게끔 한다.

while loop 안에서는 만약 target값이 mid보다 크면 target값은 전체 범위를 반으로 나눴을 때 오른쪽에 위치하기 때문에 start값을 mid보다 1 큰수로 설정하여 다시 while loop를 돌게 한다.

 

이 문제에서 이분탐색을 쓰려면 start값과 end값 설정이 중요했다. 처음에는 인덱스로 start, end값을 잡으며 문제를 풀려 하였지만 이 이후에 더이상의 접근방식이 안떠올랐다. 

 

def solution(n, times):
    
    times.sort()
    min_time = 0
    max_time = times[-1] * n

1. 해서 end의 범위를 times를 정렬했을 때 가장 시간이 많이 소요되는 입국심사대에서 모든 사람을 다 받는 경우의 수로 잡았다.

 

while min_time <= max_time:
  count = 0
  mid_time = (min_time + max_time) // 2

  for time in times:
  	count +=  mid_time // time

  	if count > n:
  		break

 

2. 이후 이분탐색의 기본 알고리즘을 따라 min_time이 max_time보다 크면 while loop을 종료하게 하였고, 루프가 돌때마다 mid_time을 계산하게 코드를 작성하였다.

또 이 문제에선 정해진 인원을 최소시간내에 입국심사를 마치게끔 하는 조건이 추가되었다.

 

3. 이는 mid_time을 times에 있는  시간들로 나눈 후 이 값들을 합치면 mid_time 시간 내에 입국심사가 가능한 인원 수가 count 되기에 for문을 이용하여 인원수를 count했다.

 

4. 이때 count수가 정해진 인원보다 많으면 더이상의 연산은 필요 없어지기에 count가 n보다 클 시에 for loop를 빠져나가게 if문으로 코드를 짜줬다.

 

 

 

실패코드 

        if count > n:
            max_time = mid_time - 1
        
        elif count < n:
            min_time = mid_time + 1
        else:
            return mid_time

 

while loop을 돌 때 count == n 이면 mid_time을 정답으로 바로 리턴하는 코드를 짯더니 test case의 모든 결과들이 실패가 나왔다. 

 

 

정답코드

        if count >= n:
            max_time = mid_time - 1
            answer = mid_time
        
        elif count < n:
            min_time = mid_time + 1

 

 

5. n보다 심사할 수 있는 인원의 수가 커도 상관은 없지만 n보다 심사할 수 있는 인원의 수가 작으면 안된다.

 

만약 처음에 짯던 실패코드를 적용시키면 count == n인 경우가 드물게 있는 경우를 제외하곤 아무것도 return시키지 못하고 loop를 빠져나와 값은 None이 나올 수 있다.

 

해서 max_time과 min_time의 범위를 줄여나가 최소 입국심사 시간(mid)값을 찾되 가능한 입국심사 명수가 n보다 큰 경우는 answer라는 변수에 mid값을 담아두고, count가 n과 일치하지 않을 경우 가장 최근에 담아뒀던 가능한 입국심사 시간(mid)을 return하면된다.

 

 

 

https://programmers.co.kr/learn/courses/30/lessons/43238

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