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

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

프로그래머스

 

문제 해설 및 풀이

'''
풀이 1.
시간초과
그냥 직접 줄을 세워보는 식으로 코드를 짜보았다.
0. 각 심사대별로 누적 시간을 저장하는 리스트(all_times)를 만든다.
1. for문으로 한 명씩 심사대에 들어가는 처리를 한다.
2. 그 다음 for문으로는 심사대 별로 넣었을 때, 누적 시간 중에 가장 큰 값이 총 걸리는 시간일 것이므로
이것이 최소인 경우의 수를 result로 뽑는다.
3. 모든 time별로 계산을 한다.

시간복잡도: O(n * len(times)) - 최대 10억 * 10만 == 100,000,000,000,000.
최대 100조번의 연산을 한다...

그냥 실험으로 짠거라 maxx는 임의로 큰수를 넣었고, 맞지 않는 상수일 것이다.
역시나 시간초과가 났다.
'''
def put_time(times, all_times):
    # 직접 줄을 세워본다.
    # 각 times를 넣었을 때 all_time의 max을 비교한다.
    maxx = 1000000000
    for i in range(len(times)):
        all_times[i] += times[i]
        if maxx >= max(all_times):
            maxx = max(all_times)
            result = [i for i in all_times]
        all_times[i] -= times[i]
    return result
    
def solution(n, times):
    # 누적된 처리 시간
    all_times = [0] * len(times)
    answer = 0
    
    for _ in range(n):
        all_times = put_time(times, all_times)
    answer = max(all_times)
    return answer


'''
풀이 2.
여기서 단서는 심사대는 독립적으로 심사가 끝나면 다음 손님을 받는 식으로 작동한다는 것이다.
따라서 모든 n명의 손님들을 처리하고 난 후에 가장 시간이 오래 걸린 심사대의 처리 시간이
전체 task의 시간을 의미한다.
따라서 이걸 최소화하면 된다는 말이다.
이코테의 공유기 설치 문제처럼 '어떤걸 start, mid, end로 놓을 것인지를 결정하면 문제는 쉬워 진다.'

따라서 '가장 오래 걸린 심사대의 처리 시간'을 매개 변수로 잡고 진행해보자.

'''
def solution(n, times):
    answer = 0
    
    # 최소값은 time의 최소값이며, 최대값(최악의 경우)는 times의 최대값에 모든 손님을 넣는 경우
    start, end = min(times), max(times) * n
    
    while start <= end:
        mid = (start + end) // 2
        # total은 mid 시간일 때의 받을 수 있는 최대 손님수이다.
        total = 0
        # 모든 심사대에 대해서 최대 mid 시간일 때의 손님수를 계산해서 더한다.
        for time in times:
            total += mid // time
        # 이 때 손님수가 n보다 많으면 모든 손님을 받을 수 있다는 뜻이 된다.
        # 따라서 answer에 mid를 저장하고, mid를 점차 줄여보자.
        if total >= n:
            end = mid -1
            answer = mid
        # 그렇지 않고 total 손님수가 n보다 적으면 모든 손님을 쳐내지 못하므로, mid를 늘린다.
        else:
            start = mid + 1
    return answer