[프로그래머스] 입국심사 (파이썬)

난이도 : Lv. 3

 

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

프로그래머스

 

📄 문제

• n명이 입국심사를 위해 줄을 서서 기다리고 있습니다.
• 각 입국심사대에 있는 심사관마다 심사하는 데 걸리는 시간은 다릅니다.
• 처음에 모든 심사대는 비어있습니다.
• 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다.
• 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다.
• 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.

 

모든 사람이 심사를 받는 데 걸리는 시간을 최소로 구하라.

 

---

💡 아이디어

• 최대 시간이 1,000,000,000^2이므로 완전 탐색 대신 이분 탐색을 활용하여 문제를 해결한다.
• 최소 시간과 최대 시간 사이에서 이분 탐색을 시행한다.
• 탐색할 중간 값(mid)을 설정한다.
• 시간을 탐색하며 몇 명이 심사 가능한지 찾는다.
  • 탐색 시간(mid) / 각 심사대의 심사 가능 시간 = 각 심사대의 심사 가능 인원
  • 각 심사대의 심사 가능 인원을 모두 더하면 현재 시각에서 심사 가능한 전체 인원이 나온다.

• 현재 시간 에서 심사 가능 인원(cnt) >= 찾는 인원(n) 이면
  • 탐색 시간(mid)을 저장하고
  • 최대 값을 탐색 시간(mid) -1로 갱신한다.

• 심사 가능 인원(cnt) < 찾는 인원(n) 이면 최소 값을 탐색 시간(mid) +1로 갱신한다.
• 위의 탐색을 반복 진행하여 n 명을 심사할 수 있는 최소 시간을 찾는다.

 

📝 문제 풀이 (Code)

def solution(n, times):
    # 최소 시간
    start = 1
    # 최대 시간
    end = 1000000000**2
    
    # 이분 탐색
    while start <= end:
        # 시간 탐색
        mid = (start + end) // 2
        
        # 심사 가능 인원 저장
        cnt = 0
        # 심사 가능 인원 탐색
        for t in times:
            # 해당 심사대에서 가능한 심사 인원
            cnt += (mid // t)
        # 심사 인원이 n보다 크거나 같으면
        if cnt >= n:
            # 시간 저장
            answer = mid
            end = mid -1
        else:
            start = mid + 1
            
    # 최소 시간 반환   
    return answer