[TIL] 250531 - 프로그래머스 입국심사

문제 설명

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분에 모든 사람의 심사가 끝납니다.

---

나의 답

def solution(n, times):
    # 최대로 걸릴 수 있는 시간 기준으로 이분탐색해 나가면서 가장 작은 시간 찾기
    start = 1
    end = max(times) * n
    min_idx = end + 1 # total == n 인 시간이 많을 거라서 조건을 만족하는 값 중 가장 작은 시간을 선택하기 위한 변수
    
    while start<=end:
        mid = (start + end) // 2
        total = sum(mid//i for i in times)
        if total >= n:
            end = mid-1
            min_idx = min(min_idx,mid) # 조건을 만족하는 값 중 가장 작은 mid 저장
            continue
        elif total < n:
            start = mid +1 
            continue
    return min_idx

 

• 사용된 알고리즘 : 이분 탐색(Binary Search)
  • 이 문제는 정렬된 배열에서 특정 값을 찾는 게 아니라, 시간 범위(1분 ~ 최대 예상 시간)를 기준으로 이분탐색을 해서 "n명을 심사할 수 있는 최소 시간"을 찾는 문제임.
  • 처음에는 아래처럼 정답이 될 수 있는 모든 시간을 리스트로 만들어서 정렬한 뒤, n번째 수를 답으로 반환했는데 시간 초과가 나서 이분탐색으로 전략을 변경함.

def solution(n, times):
    answer = 0
    li = [] # 각 심사대별로 n명을 상대할때 걸리는 시간 기록
    for i in range(1,n+1):
        for j in times:
            li.append(j*i)
    li = sorted(li)
    answer = li[n-1]    
    return answer

• 이분탐색 중에서도 lower_bound 패턴을 사용함.
  • lower_bound 란?
    • 정렬된 범위에서 주어진 조건을 처음으로 만족하는 최소값의 위치 또는 값을 찾는 방법
  • 이걸 위해 사용한게 min_idx 변수임.
  • total == n 을 만족시키는 시간은 많을수도 있으므로 lower bound를 찾아야 했음.
    • ex. 아래의 경우 28분, 29분이 다 total == n 을 만족시키므로 28을 찾아야함.

      n	times
      6	[7, 10]