[Level 3] 입국심사

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

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

---

접근

이분탐색이 무엇인지는 알았지만 비슷한 유형의 문제만 풀어서 아직 완벽하게 이해하지 못했다.

이 문제는 고득점kit에 이분 탐색으로 분류되어 있다. 그래서 문제를 읽고 이분탐색으로 접근을 하려고했는데 도대체 어떻게 접근을 해야할지 감이 잡히지 않았다.

 

감이 잡히지 않은 이유

첫 번째는 이분 탐색을 완벽히 이해하지 못해서다. 왜 left와 right값을 주고 mid값을 통해 탐색을 진행하는지 겉핥기식으로 알았다. 

두 번째는 입력으로 주어지는 n과 times에만 집중되어 있었다. 즉 n을 어떻게해야 이분탐색이 될까? times를 어떻게해야 이분탐색이 될까만 생각을 하였다.

 

이분탐색은 특정범위 안에서 답이 될 수 있는 범위를 좁혀나가는 것이다.

이 문제에서는 1분부터 times에 있는 시간 중 최댓값x사람의 수만큼 탐색의 범위를 정한다.

그리고 이 안에서 n명의 사람들이 심사를 받는 최솟값을 구하도록 한다.

 

구현

- 먼저 탐색의 범위를 정한다. left는 최소의 시간인 1분, right는 제일 오래걸리는 심사관이 n명을 모두 심사하는 하는 것으로 times의 최댓값 x n을 해주었다.

- 이제 left와 rigth로 mid를 구하여 탐색의 범위를 좁혀나간다.

- mid는 n명의 사람을 심사하는데 걸리는 시간이다. 이를 times에 있는 시간으로 모두 나누면 각 심사관이 몇 명을 심사할 수 있는지 나오게된다.

- 해당 값을 count에 저장하고 n명 이상일 때 종료시킨다.

- 만약 count가 n 이상이라면 최종해인 answer에 mid를 대입하고 오른쪽의 범위를 좁힌다. count가 많다는 것은 그만큼 심사하는 시간이 크고 한 심사관이 해당 시간동안 심사할 수 있는 사람이 많다는 것이다. 

- 만약 count가 n 미만이면 심사시간이 더 필요한 것이기 때문에 왼쪽의 범위를 좁힌다.

- 이 과정에서 left가 right 이상이 된다면 탐색이 종료되고 answer에 최솟값이 담기게 될 것이다.

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

    return answer