💡문제 분석 요약

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

• 입국심사를 대기하는 n명의 사람이 각 심사관이 한 명을 심사하는데 걸리는 시간에 따라 입국심사대에서 심사를 받는데 걸리는 최소시간을 구하여라
• 매개변수 = 입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times

💡 n = 6

times = [7, 10]

0분 → 소요시간 7분, 10분 창구에 1,2 입국심사

7분 → 소요시간 7분 창구에 3 입국심사

10분 → 소요시간 10분 창구에 4 입국심사

14분 → 대기시간 7분 창구에 5 입국심사

1)

20분 → 대기시간 10분 창구 6 입국심사

입국심사 완료 → 30분

2)

21분 → 대기시간 7분 창구 6 입국심사

입국심사 완료 → 28분

최소시간인 28분 return

💡알고리즘 설계

• start = 1 한 창구에서 모든 고객을 받는 경우 중 가장 최소의 경우인 end = n * min(times) 로 두어 이진 탐색을 한다.
• mid = (start + end) // 2 로 해당 값에 총 몇명이 창구를 사용할 수 있는지 계산해야한다.
• 이를 위해 mid를 times의 각 요소로 나눠주어 해당 시간동안 각각 몇명의 사람을 처리할 수 있는지 계산하고 더한다(s에 저장).
  • s ≥ n : n보다 더 많은 사람을 처리할 수 있다는 뜻이므로 start~end 중 왼쪽을 탐색해야한다. 따라서 end = mid -1
  • s < n : n보다 더 적은 사람을 처리할 수 있다는 뜻이므로 start~end 중 오른쪽을 탐색해야함. 따라서 start = mid + 1
• start > end 가 되면 loop escape
• start return

💡코드

def solution(n, times):
    start = 1
    end = n * min(times)

    while start <= end : 
        mid = (start + end) // 2
        s = 0
        for t in times :
            s += mid//t
        if s >= n : end = mid - 1
        else : start = mid + 1
    return start

💡시간복잡도

• times의 최솟값을 M, 사람 수 n을 N이라고 한다면 1부터 N까지 이진탐색하므로 O(logN)
• 위 loop 안에서 times길이(M)만큼 for loop를 돌기 때문에 O(M)
• 따라서 시간복잡도는 O(MlogN)

💡 틀린 이유

• 시간초과

💡 틀린 부분 수정 / 다른 풀이

• 처음에 문제를 접했을 때 어떻게 이분탐색을 사용해야할지 몰라 아래와 같이 times의 모든 요소들을 1~n배하여 리스트를 만들고 해당 리스트의 [n-1]번째 요소를 return했다. 하지만 이런 방법을 사용할 경우 O(N*M)으로 시간초과가 발생한다. 따라서 이분탐색을 사용하도록 수정하였다.

def solution(n, times):
    wait = []
    mini = min(times) * n
    times.sort()
    for t in times :
        for i in range(1, n) :
            a = t * i
            if mini < a :
                break
            wait.append(a)
    
    wait.sort()
    # print(wait)
    return wait[n - 1]

💡 느낀점 / 기억할정보

• 알고리즘을 다시 구상하며 start, end의 구간은 쉽게 떠올려졌지만 왼쪽, 오른쪽 탐색을 정하는 기준을 생각하는 것이 어려웠다. 또한 이분탐색 문제들을 많이 풀어보지 않아 이게 왜 이분탐색 문제지? 라는 생각을 많이 했던 것 같다. 비슷한 유형의 문제들을 많이 접하여 빠르게 알고리즘을 떠올릴 수 있도록 연습해야겠다.
• 디버깅을 통해 start가 정답인 것을 알아냈는데 알고리즘 측면에서 왜 start가 되어야하는지 잘 모르겠다. 좀 더 공부해보자