[프로그래머스] 이분탐색 - 입국심사 (Python3, 파이썬)

1. 문제

문제 요약

• 모든 사람이 입국심사를 받는데 걸리는 시간의 최솟값을 구하자.
• 주어지는 값 : 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times, 입국심사를 기다리는 사람 수 n
• 사용되는 공식 : 입국심사를 받을 수 있다고 해서 무조건 받으면 안 되고 더 적게 걸리는지 확인 후 받아야 함.

2. 입출력 예시와 설명

3. 코드

- 내가 생각한 아이디어

sort 함수로 정렬을 한 뒤 배열의 크기를 len 함수로 구한다. 배열의 크기를 n으로 나눈 뒤 최댓값에 몫을 곱하고 나머지는 가장 작은 배열의 0번인덱스의 값을 1번 더 했을 때를 계산하여 구한다.일단 이렇게 코드를 짜기 시작했는데 이 아이디어는 예시처럼 배열의 크기가 2일 때로 상상하여 만들었기 때문에입국 심사대에서 걸리는 시간 차가 2배 이상일 경우는 고려하지 못 했다. 만약 그럴 경우 절대 정답이 안 나올 것 같았다.그래서 코드를 작성하다가 중지하고 다른 사람들이 직접 짠 알고리즘을 참고하기로 했다.

def solution(n, times):
    answer = 0
    point = len(times)
    times.sort()
    a = int(n/point)
    b = n%point

 

 

- 정답 코드 (참고한 코드)

def solution(n, times):
    start = 0 #시작점
    end = max(times) * n #끝점
    
    answer = 0
    while (start <= end):
        people = 0
        mid = (start+end) // 2
        for x in times:
            if mid > x:
                people += (mid//x) # 심사가능한 사람 수
        # n명 이상으로 심사 가능한 경우(왼쪽 탐색)        
        if people >= n:
            answer = mid # 적어도 6명이 심사가 가능해야 하므로 여기서 저장
            end = mid - 1
        # n명 미만으로 심사 가능한 경우 (오른쪽 탐색)
        else:
            start = mid + 1
            
    return answer

이분탐색을 어디에 써야 할지 감이 안 잡혔는데 다른 분들의 코드를 참고하다보니 입국심사 시간에 써야 한다는 것을 알 수 있었다. 코드를 천천히 살펴보면 start와 end가 최솟값과 최댓값이고 중간값이 mid로 start와 end를 더 해 2로 나눠준 값이다. 그 후 for문으로 times 리스트의 값들을 하나씩 사용하여 mid보다 작으면 mid를 그 값으로 나눈 몫을 people에 더해주는 방식으로 했다. 그 후 if문으로 people의 값을 n과 비교하여 결과에 따라 answer에 넣어주고 start나 end의 값을 mid+1이나 mid-1로 재설정해주었다.

 

참고 링크 : https://sanghyeok.tistory.com/7