프로그래머스 Lv3 문제입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.

문제

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

[나의 풀이]

⌛ 미구현

def solution(n, times):
    
    answer = -1
    gates = {str(time):0 for time in times}
        
    while n>-2:
        answer += 1

        tmp_gates = []
        
        for gate,rest in gates.items():
            if gates[gate]==0: 
                tmp_gates.append(gate)
                n -= 1
        tmp_gates.sort(reverse=True)
        
        for tmp_gate in tmp_gates:
            gates[tmp_gate] = int(tmp_gate)
            # n -= 1

        for gate,rest in gates.items():
            gates[gate] -= 1

    return answer 

입국 심사인원(n)과 입국심사대별 소요시간 리스트(times)가 주어질 때, 완료된 입국심사대를 우선으로 활용하여 모든 입국 심사인원을 심사할 수 있는 최소값을 구하는 문제입니다.

문제를 정의하는 것 자체는 어렵지 않았지만 이를 구현하는데는 어려움이 있었습니다. while문으로 매 시간별로 완료된 입국심사대를 찾고 빈 입국심사대에 인원을 넣는 방식으로 시도하였지만 입력되는 최대값의 시간복잡도를 해결하기 어려워 다른 풀이를 참고하였습니다.🐥🐥🐥

[다른 사람의 풀이1]

def solution(n, times):
    answer = 0    
    start, end = 1, max(times)*n
    
    while start<=end:
        
        mid = (start+end)//2
        tmp = 0
        
        for time in times:
            tmp += (mid//time)
                
        if n<=tmp:
            end=mid-1
            answer = mid
        else:
            start=mid+1
    
    return answer

이분탐색을 활용하여 구하는 방식입니다.

매 시간을 카운트하여 순차적으로 확인하는 것이 아닌 심사하는 최솟값, 최대값 범위를 정하고 이분탐색하여 mid 값을 찾아나가는 것입니다.

최대값은 가장 오래걸리는 심사대*n을 기준으로 정하며 n명 모두 심사할 수 있는 최솟값을 갱신하며 최소 시간을 구할 수 있었습니다.

입력값이 1,000,000,000과 같이 아주 큰 수일 때 이분탐색을 먼저 떠올려야함을 알 수 있었습니다.🦙🦙🦙

[다른 사람의 풀이2]

def available(n, times, t): # can evaluate n people within t time
    temp = 0
    for time in times:
        temp+= t//time
        if temp >=n:
            return 1
        else : 
            continue
    return 0

def solution(n, times):
    max_t = max(times)*n
    min_t = 1

    def search(min_t, max_t):
        # when will it return? 
        if ((max_t + min_t)//2 == min_t):
            if available(n, times, min_t):
                return min_t
            else:
                return max_t

        mid_t = (max_t + min_t)//2
        flag = available(n, times, mid_t)

        if flag == 1:
            return search(min_t, mid_t)
        else : # flag == 0
            return search(mid_t, max_t)

    return search(min_t, max_t)

이분탐색을 활용한 다른 표현의 풀이입니다.🐪🐪🐪

감사합니다.