[프로그래머스] 입국심사 (Python/파이썬/이진 탐색)

문제 설명

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

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

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

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

 

 

문제 풀이

이분 탐색(이진 탐색)

• 이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법

 

동작 방식

1. 배열의 중간 값을 가져오기
2. 중간 값과 검색 값을 비교

      2-1. 중간 값이 검색 값과 같다면 종료 (mid = key)

      2-2. 중간 값보다 검색 값이 크다면 중간값 기준 배열의 오른쪽 구간을 대상으로 탐색(mid < key)

      2-3. 중간 값보다 검색 값이 작다면 중간값 기준 배열의 왼쪽 구간을 대상으로 탐색 (mid > key)

   3. 값을 찾거나 비어 있을 때까지 반복

 

 

문제의 조건

• 입국 심사를 기다리는 n명을 모두 심사하는데 걸리는 최소 심사 시간

 

접근 방법

• 임의의 시간 동안 몇 명이 심사 받을 수 있는지 확인하고 이 값을 최소로 만들기
• 시간의 최소, 최대 범위를 구하고 중간 값이 n명을 심사 할 수 있는 시간인지 확인하며 이분 탐색을 진행
• 중간 값 시간 동안 ,
• n명보다 많이 심사 가능 -> 중간값 기준 왼쪽 범위 탐색
• n명보다 적게 심사 가능 -> 중간값 기준 오른쪽 범위 탐색
• 임의의 시간동안 몇 명을 심사 할 수 있는지 확인하는 방법

임의의 시간동안 심사 가능한 사람 수 =  임의의 시간/ 각 심사관들이  심사하는데 걸리는 시간

• 예) 임의의 시간 30분  각 심사관들이 심사하는데 걸리는 시간[7, 10]
• 7 = (30 / 7) + (30 / 10 )
• 30분 동안 7명 심사 가능

 

풀이 설명 그림

def solution(n, times):
    answer = 0
    # right는 가장 비효율적으로 심사했을 때 걸리는 시간
    # 가장 긴 심사시간이 소요되는 심사관에게 n 명 모두 심사받는 경우이다.
    left = min(times)
    right = max(times)*n
    while left <= right:
        mid = (left+ right) // 2
        checked = 0
        for time in times:
            # people 은 모든 심사관들이 mid분 동안 심사한 사람의 수
            checked += mid // time
            # 모든 심사관을 거치지 않아도 mid분 동안 n명 이상의 심사를 할 수 있다면 반복문을 나간다.
            if checked >= n:
                break
        
        # 심사한 사람의 수가 심사 받아야할 사람의 수(n)보다 많거나 같은 경우
        if checked >= n:
            answer = mid
            right = mid - 1
        # 심사한 사람의 수가 심사 받아야할 사람의 수(n)보다 적은 경우
        elif checked < n:
            left = mid + 1
            
    return answer

 

 

문제 출처:

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

 

 

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