[Python/코테] 프로그래머스 입국심사

프로그래머스 입국심사

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

프로그래머스

알고리즘 설계

💡idea.

제한 사항을 확인해보면 기다리는 사람, 걸리는 시간 등의 최대값이 꽤 큰 것을 확인할 수 있다. 반복문을 잘못 사용하면 쉽게 시간초과가 발생한다.

각 사람에 대해 어떤 심사대에서 심사를 받을지를 결정하는 대신, 특정 시간 내에 모든 사람이 심사를 받을 수 있는지를 판단하는 방식으로 접근할 수 있다. 즉 시간을 기준으로 가능한 사람 수를 계산한다. 

조건을 만족하는 최소 시간을 찾기 위해, 이진 탐색을 활용할 수 있다.

 

🎲step.

1. 각 심사관이 기준 시간동안 처리할 수 있는 사람 수를 계산한다.

2. n명보다 많거나 적다면 기준 시간을 줄이거나늘리면서 다시 1번 검사를 반복한다. 

알고리즘 구현

def solution(n, times):
    # 최소 시간
    left = 1
    # 최대 시간
    right = max(times) * n
    
    while left < right:
        mid = (left + right) // 2
        # mid 시간 내에 처리할 수 있는 총 사람 수 계산
        total = sum(mid // time for time in times)
        
        # 총 처리할 수 있는 사람 수가 n 이상이면, 시간을 줄여도 될 가능성
        if total >= n:
            right = mid
        else:
            # 그렇지 않으면, 더 많은 시간이 필요
            left = mid + 1
    
    return left

출처: chatgpt

문제 예시에도 나왔듯, 누군가는 더 짧은 심사대를 이용하기 위해 기다렸다가 심사를 받는 경우도 있다. 이 경우는 mid시간으로 심사 시간을 나눴을 때의 나머지가 될 것이다.

즉 아래와 같이 반복되며 최적의 mid를 구할 수 있다.

 

• mid = (left + right) // 2 = (24 + 30) // 2 = 27
• 각 심사관이 27분 동안 처리할 수 있는 사람 수:
  • 첫 번째 심사관: 27 // 7 = 3명
  • 두 번째 심사관: 27 // 10 = 2명
  • 총 처리할 수 있는 사람 수: 3 + 2 = 5명
• total < n이므로, left = mid + 1 = 28

 

• mid = (left + right) // 2 = (28 + 30) // 2 = 29
• 각 심사관이 29분 동안 처리할 수 있는 사람 수:
  
  • 첫 번째 심사관: 29 // 7 = 4명
  • 두 번째 심사관: 29 // 10 = 2명
  • 총 처리할 수 있는 사람 수: 4 + 2 = 6명
• total >= n이므로, right = mid = 29

 

나다어

나는 다음에 어떻게 풀까

• 이 문제에서는 특정 시간 내에 모든 사람이 심사를 받을 수 있는지를 판단하는 방식으로 접근할 수 있다고 했다. 출력해야 하는 값이 '걸리는 시간' 이므로, 출력해야 하는 값을 기준으로 문제 해결의 힌트를 얻을 수 있을 것 같다.
• --> 너무 복잡하면 정반대로 생각해보자 !
  
• 이진탐색은 정렬된 배열에서 값을 찾을 때 뿐만 아니라, 조건을 만족하는 최적/최대최소(경계) 값을 찾을 때 효율적이다. 즉 특정 조건을 만족하는 값을 찾는 문제에서 많이 쓰인다.