Programmers 입국심사

💡문제 분석 요약

• N명의 사람들이 심사관들에게 심사를 받는 최소 시간을 구해야한다.
• 심사관마다 심사를 보는 시간은 제각기 다르다.
• 이때 주의할 점은, 당장 내가 심사를 받을 수 있는 상황이더라도 잠시 기다렸다가 심사를 더 짧게 보는 사람에게 가는 것이 이득일 수 있다는 것이다. ex) 당장 가서 100분 심사받기 vs 1분 기다렸다가 20분 심사받기

💡알고리즘 설계

• 잠시 기다리는 대기시간을 고려한다는 점에서 DP로 풀 수 있다고 생각했지만, 입력 값이 10억인 것을 보고 안되는 것으로 판단했다...
• 이분탐색을 이용해본다.

💡코드

def solution(n, times):
    
    # left = 최소시간 , right = 최대시간
    
    left = 1 # 최소시간은 1분이상이라고 문제에 명시
    right = max(times) * n # 모든 사람이 가장 느린 심사관에게 심사를 받을 때가 최대시간
    
    while left < right:
        mid = (left + right) // 2
        # total = 각 심사관이 mid 시간 동안 심사할 수 있는 사람의 수를 계산
        total = sum(mid // time for time in times)
        
        # total이 n 이상이면 가능한 시간을 "줄이기" 위해 right = mid
        if total >= n:
            right = mid
        # total이 n 미만이면 가능한 시간을 "늘리기" 위해 left = mid + 1
        else:
            left = mid + 1
    # 최종적으로 left가 최소시간을 가리키게 됨.
    return left

💡시간복잡도

• 이분탐색이므로 O(log N)

💡 틀린 이유

• 보자마자 DP로 푸는 거라고 생각했다. if 빈 심사관이 생겼다면: time = min(빈 곳에 바로 들어가기, 기다렸다가 더 짧은 사람 들어가기) 이렇게 생각을 했는데.... 심사관이 10만명? 그럼 모든 심사관에 대해서 체크해야하는지도 의문이었고 막막했다.

💡 틀린 부분 수정 or 다른 풀이

total = sum(mid // time for time in times)

이걸 생각해내는 게 핵심이지 않았나 싶다. 결국 total값을 구하고, 이를 n과 비교해서 이분탐색을 해나가야했다.

💡 느낀점 or 기억할정보

• n이 10억 ... 너무 크다고 생각은 했는데 이럴 땐 거의 확정적으로 O(log N)을 떠올려야하는 것 같다.
• 문제를 잘 못풀었고, 이해를 못했다는 느낌을 받는다. 나중에 다시 시도해봐야한다. N이 지나치게 큰 것을 보고 이분탐색을 떠올려도 아마 풀지 못했을 것 같다...