[이진탐색] 프로그래머스_입국심사

n명이 입국심사를 위해 줄을 서있고, 입국심사관이 한 명을 심사하는 데 걸리는 시간이 담긴 배열 times가 있다. 기다리는 시간과 심사 시간까지 합해서 모든 사람이 심사를 받는 데 걸리는 시간의 최솟값을 return 해야 한다.

입출력 예

n	times	return
6	[7, 10]	28

입출력 예 설명

가장 첫 두 사람은 바로 심사를 받으러 갑니다.
7분이 되었을 때, 첫 번째 심사대가 비고 3번째 사람이 심사를 받습니다.
10분이 되었을 때, 두 번째 심사대가 비고 4번째 사람이 심사를 받습니다.
14분이 되었을 때, 첫 번째 심사대가 비고 5번째 사람이 심사를 받습니다.
20분이 되었을 때, 두 번째 심사대가 비지만 6번째 사람이 그곳에서 심사를 받지 않고 1분을 더 기다린 후에 첫 번째 심사대에서 심사를 받으면 28분에 모든 사람의 심사가 끝납니다.

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

프로그래머스

---

문제를 보고 가장 먼저 든 풀이 방법은 처음 두 사람은 바로 들어가고, return할 값에  times 리스트에서 가장 작은 시간 더하기, 그 시간의 2 배수와 times 리스트에서 그다음으로 작은 시간과 비교하기, return 할 값에  골라진 time 더하기,... 와 같이 같은 방식을 이어가려고 했습니다.

하지만 이진탐색 문제이니... 이진탐색으로 풀어나갈 수 있는 방법을 생각해 봤습니다.

바로, 하나씩 더해가며 심사시간을 구하는 것이 아닌, 임의의 시간 동안 몇 명이 심사받을 수 있는지 확인하는 것입니다.

최종적으로 시간을 return해야해서 한 명, 한 명 심사하며 걸리는 시간을 6명이 될 때까지 시간을 더해주려고 했는데, 그게 아닌, 임의의 시간 동안 몇 명이 심사할 수 있는지를 계산하고, 그 사람 수가 6명인지만 확인하면 되는 겁니다!

임의의 시간 mid동안 심사할 수 있는 사람의 수가 주어진 n명 보다 많다면, 중간값 왼쪽을 확인하고,

임의의 시간 mid동안 심사할 수 있는 사람의 수가 주어진 n명 보다 적다면, 중간값 오른쪽을 확인하면 되겠죠

이진탐색을 할 때는 이진 탐색 범위와 탐색 기준을 알아내는 것이 중요합니다.

저는 다음과 같이 범위와 기준을 정했습니다.

범위 : 최대로 걸리는 시간 = times리스트에서 가장 오래 걸리는 시간 * n명

기준 : mid 시간 동안 심사한 사람의 수가 n보다 크면 왼쪽 탐색(end = mid-1), mid 시간 동안 심사한 사람의 수가 n보다 적으면 오른쪽 탐색 (start = mid+1)

그럼 이를 바탕으로 코드를 작성해보겠습니다.

---

def solution(n, times):
    answer = 0
    start = 1
    end = max(times)*n
    while start<=end:
        mid = (start+end)//2
        # 검사한 사람의 수 체크
        people = 0
        
        for t in times:
            #mid 시간동안 심사 가능한 사람의 수
            people += mid//t
            #모든 심사관을 거치지 않아도, mid시간동안 n명 이상을 심사하면 반복문 종료
            if people >= n:
                break

        #mid 시간동안 심사가능한 사람의 수보다 찾고자 하는 값이 작거나 같은 경우(왼쪽 확인)
        if people >= n:
            answer = mid
            end = mid-1             
        #mid 시간동안 심사가능한 사람의 수보다 찾고자 하는 값이 큰 경우(오른쪽 확인)
        elif people < n:
            start = mid + 1
            
    return answer

재귀적 방법이 아닌 반복문을 사용해서 이진 탐색을 해주었는데요! 이때는 while(start <=end)로 하면 됩니다. 만약 start가 end보다 크다면 검색 범위가 없어진 것이므로 반복문을 종료하는 것입니다.
그리고 그 반복문 안에서 mid를 설정하고, 찾은 경우, mid 시간 동안 심사가능한 사람의 수보다 찾고자 하는 값이 작은 경우(왼쪽 확인), mid 시간동안 심사가능한 사람의 수보다 찾고자 하는 값이 큰 경우(오른쪽 확인)를 구분해서 탐색범위를 좁혀나가면 됩니다.

이때, mid를 통해 심사가능한 사람의 수를 계산하는 for문을 작성해야 합니다. 

start, end, mid가 모두 시간이지만, n명은 시간으로 나타낼 수 없습니다. 하지만, n명을 심사할 동안의 최소 시간을 구해야 하기 때문에 탐색 기준인 mid를 통해 심사 가능한 사람의 수를 계산하는 for문을 별도로 작성해서 탐색해주어야 합니다.

for문과 if문의 흐름에 대한 이해가 쉽게 되지 않아 아래에 절차를 그려봤습니다!

이를 통해 이진탐색을 기반으로 매우 빠르게 계산할 수 있게 되었습니다!

문제만 보고 이진탐색을 떠올리기 힘들었다.. 그냥 처음부터 하나씩 시간을 계산해 나가며 최소를 구할 생각이었다. 하지만 이진탐색으로 구현하니 매우 간단하고 빠르게 구현된다는 것을 깨달아 이진탐색을 확실히 내 것으로 만들어야겠다고 생각했다. mid를 통한 계산 방식을 더 공부해야 될 거 같다!

재밌었다~~