프로그래머스 - 이진탐색_입국심사(MJ)

📖Problems

코딩테스트 연습 > 고득점 kit > 이분탐색 > 입국심사 LEVEL 3문제입니다.

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

입출력 예 설명

가장 첫 두 사람은 바로 심사를 받으러 갑니다.

7분이 되었을 때, 첫 번째 심사대가 비고 3번째 사람이 심사를 받습니다.

10분이 되었을 때, 두 번째 심사대가 비고 4번째 사람이 심사를 받습니다.

14분이 되었을 때, 첫 번째 심사대가 비고 5번째 사람이 심사를 받습니다.

20분이 되었을 때, 두 번째 심사대가 비지만 6번째 사람이 그곳에서 심사를 받지 않고 1분을 더 기다린 후에 첫 번째 심사대에서 심사를 받으면 28분에 모든 사람의 심사가 끝납니다.

🔍Conception

n명이 입국심사를 받아야 함. 심사를 하는데 걸리는 시간을 나타낸 배열 times를 보고 최소가 되도록 해야 한다.

⇒ 이 문제는 이진탐색 문제로, 먼저 이진탐색 알고리즘에 대해 다시 짚고 넘어갈 필요가 있다.

이분탐색(Binary Search) 알고리즘의 기본 구조

chatGPT

• Set left and right pointers to the first and last indices of the array.
• While the left pointer is less than or equal to the right pointer.
  • Calculate the middle index by adding the left and right pointers and dividing by 2.
  • If the middle element is equal to the target, return its index.
  • If the middle elements is less than the target, set the left pointer to the middle index plus one.
  • If the middle elements is greater than the target, set the right pointer to the middle index minus one.
• If the target is not found, return -1.
• 배열의 첫 번째 및 마지막 인덱스에 대한 왼쪽 및 오른쪽 포인터를 설정합니다.
• 왼쪽 포인터가 오른쪽 포인터보다 작거나 같은 경우.
  • 왼쪽(left)과 오른쪽(right) 포인터를 추가하고 2로 나누어 중간 지수를 계산합니다.
  • 중간 요소(mid)가 대상(target)과 같으면 인덱스를 반환합니다.
  • 중간 요소가 목표값보다 작으면 왼쪽 포인터를 가운데 인덱스에 1을 더한 값으로 설정합니다.
  • 중간 요소가 목표값보다 크면 오른쪽 포인터를 가운데 인덱스에서 1을 뺀 값으로 설정합니다.
• 대상을 찾을 수 없으면 -1을 반환합니다.

🔍Institution

이진탐색에서 정해야 할 것은 범위는 어떻게 설정할지, 무엇을 탐색할지, 어떤 기준으로 탐색할지이다.

• 범위 : 심사를 하는데 총 걸리는 시간을 탐색해야 한다. 따라서 최소가 되는 시간부터 가장 오래걸리는(최대가 되는)심사시간으로 설정한다.
• 무엇을 탐색하는가? → 최종 return해야 하는 것이 몇 분이 걸렸는지 최소 시간을 return한다. 따라서, 탐색해야 하는 대상은 걸리는 ‘시간’이다.
• mid : 모든 심사관들에게 주어진 시간이다.
• 기준 : mid 동안 심사를 완료한 사람의 수(completed)가
  1. 심사 받아야할 사람의 수(n)보다 많거나 같을 경우에는 시간이 충분했던 것이므로 주어진 시간을 줄이고 ( right = mid - 1 -> right 를 줄이면 left와 right의 중간 값인 mid 도 줄어드니까 주어진 시간이 줄어든다.)
  2. 심사 받아야할 사람의 수(n)보다 적은 경우에는 시간이 부족했던 것이므로 주어진 시간을 늘린다. (left = mid + 1)

이때, 비교해야 하는 값, 즉 몇 명을 탐색했는지 어떻게 아느냐도 관건이다.

• mid = 모든 심사관들에게 주어진 시간이므로,
• mid // 심사받는데 걸리는 시간 ⇒ 검사받은 사람의 수가 된다.

🔍Approach

🚩My submission

1. left는 times에서 가장 작은 시간을 넣어준다. right는 가장 긴 심사시간이 걸리는 경우, 즉 times에서 가장 큰 시간 * n(인원 수)의 값을 넣어준다.
2. mid를 설정한다. mid는 left+right // 2이다.
3. for문을 이용하여 mid분동안 입국심사한 사람의 수를 구하여 completed에 저장한다.
   • 이때, completed가 n과 같으면 더 구할 필요가 없으므로 break를 걸어 종료한다.
4. 만약 심사한 사람의 수가 n보다 작을 경우, left의 값을 변경해준다. mid를 기준으로 오른쪽으로 가야 하므로 mid + 1
5. 만약 4번이 아니라면(=심사한 사람의 수가 n보다 크거나 같을 경우), right의 값을 변경해준다. mid를 기준으로 왼쪽으로 가야하므로 mid - 1
   • 또한, 같은 경우도 포함되어 있으므로, answer에도 mid값을 집어넣어준다.
6. 위 ~ 과정을 left<=right까지 반복한다.
7. answer를 return한다.

def solution(n, times):
    answer = 0
    left = min(times)
    right = max(times) * n
    
    while left <= right:
        mid = (left + right) // 2
        completed = 0

        for i in range(len(times)):
            completed += (mid // times[i])
            if completed == n:
                break
            
        if completed < n:
            left = mid + 1
        else: # complete >= n
            answer = mid
            right = mid - 1
    return answer

• 계속 에러가 났었는데 그 이유는 answer = mid와 return answer를 하지 않아서였다.
• complete ≥ n은 즉 complete == n인 것도 포함하기 때문에 값을 answer에 넣어주어야 한다.

💡TIL

• 어떤 것을 target값으로 설정해야 하는지 몰라서 헤맸던 문제였다. 앞으로 target값을 모르겠을 때는 return을 무엇을 해야 하는지 보면 된다는 것을 명심하자!
• 이진 탐색은 ‘이분 탐색의 범위는 무엇으로 할지’와 ‘이분 탐색의 기준을 무엇으로 할지’를 잡아야 한다.