[Programmers/ level3] 입국심사🔔

👩문제

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

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

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

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

👩제한사항

• 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
• 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
• 심사관은 1명 이상 100,000명 이하입니다.

👩입출력 예

n	times	return
6	[7, 10]	28

👩입출력 예 설명

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

🙋‍♀️접근 방법

🔔이분탐색?

• 정렬되어 있는 배열에서 범위를 절반씩 줄여가면 탐색을 진행하는 방식이다.
• 시간 복잡도: O(logN)

예: [1, 2, 3, 4, 5, 6, 7, 8]에서 7을 찾는 경우

• 우선 이분탐색에서는 탐색 범위의 시작과 끝을 나타내는 변수들과 범위의 중간값을 나타내는 변수가 필요하다.

• 첫 단계에서 범위의 시작과 끝은 각각 0과 8이고, 중간값은 4가 된다.

• 찾고자 하는 값이 중간값보다 큰 값이므로 범위를 중간값 이후로 재설정해야 한다.
  • 범위의 시작이 중간값 + 1인 5가 된다.
  • 찾고자 하는 값 < 중간값: 범위의 끝을 중간값-1로 변경하여 범위를 재설정 한다.
• 이와 같은 방식을 범위의 시작과 끝이 역순(시작 > 끝)이 되기 전까지 반복한다.

🔔문제 해결

• 해당 문제의 핵심은 🌟특정 시간동안 심사관들이 각각 몇 명의 사람을 심사했는지🌟이다.
  • 즉, 🌟🌟특정 시간이 주어진다면 각 심사관들이 심사할 수 있는 사람의 수를 구할 수 있다. 이를 다 더했을 때 n명이 되는 시간을 구하면 되는 것이다!🌟🌟

  
  

• 여기서 이분탐색을 적용한다면 다음과 같다.
  • 탐색할 대상은 심사를 받는데 걸리는 시간이 된다.
  • 탐색 범위는 0 ~ 심사를 받는데 걸리는 최대 시간

  • 이분탐색을 진행하면서 특정 시간에 심사관들이 심사할 수 있는 인원 수가 n이 되는 시점을 구한다.

    🔔 여기서 주의할 점이 있다.🔔

    • 특정 시간에 각 심사관이 심사할 수 있는 사람의 수는 단순히 몫을 통해서 파악하기 때문에 n이 되는 시간대 여럿 존재할 수 있다는 점이다.
    • 따라서 이 중 최솟값을 구해 문제의 답을 구해야 한다.

👩 그렇다면 코드를 통해서 더 자세하게 살펴보자!

def solution(n, times):
    str = 0
    end = n*times[-1]
    mid = end//2
    check = 0
    answer = 0
    
    while str <= end:
        for i in times: #🔔해당 시간대에 심사관들이 심사할 수 있는 총 인원
            tmp = mid//i
            check += tmp   
        if check >= n:
            end = mid-1
            if answer == 0:
                answer = mid
            else:
                answer = min(answer, mid) #🔔n이 되는 시간대 중 최솟값을 구한다.
        else:
            str = mid+1
        mid = (str+end)//2
        check = 0
        
    return answer

👩‍💻배운 점

이번 문제를 통해서 잊고 지냈던 이분탐색을 다시 한 번 되짚고 넘어갈 수 있었다.

O(N)의 시간복잡도를 가지는 순차탐색보다는 이분탐색(O(logN))을 활용하는 것이 훨 효율적이라는 것을 다시 한 번 느낄 수 있었고, 이분 탐색의 경우, 정렬된 배열을 기준으로 진행한다는 점도 알게 되었다.

🙇‍♀️풀이에 부족한 부분이 있다면 말씀해주세요! 감사합니다!

📃 참고

• https://programmers.co.kr/learn/courses/30/lessons/432380
• https://satisfactoryplace.tistory.com/39
• https://minnnne.tistory.com/32