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

문제

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

[나의 풀이]

⌛ 시간 초과 (미구현)

from bisect import bisect_left

def solution(n, times):
    
    times = sorted(times)
    answer = 0
    audits = []
    
    # for i in range(len(times)):
    #     if i < len(times):
    #         audits.append(times[i])
    #         n -= 1
    #     else:
    #         audits.append(0)

    audits = [0 for i in range(len(times))]
    
    n -= len(audits)
    
    print(audits)
    
#     while n!=0:
        
#         answer += 1
#         audits = [audits+1 for audits in audits]
        
#         for audit in audtis:
            
        
    
    return answer

문제를 정의는 어렵지 않았지만 구현하는데 난이도가 상당했던 문제였습니다.

심사에 걸리는 시간이 다른 입국 심사대에 n명이 심사할 때 걸리는 최소한의 시간을 구하기 위해 그리디로 접근하였습니다.

모든 사람이 입국 심사를 완료할 때까지 1초 간격으로 시간을 누적시키며 현재 입국 심사가 완료된 곳이 다음 입국 심사까지 걸리는 시간이 가장 적을 때 다음 사람을 심사하는 방식으로 구현하고 싶었습니다. 하지만 이 아이디어를 코드로 표현하는데 어려움이 있어 다른 풀이를 참고하였습니다.

[다른 사람의 풀이1]

def solution(n, times):

    # times.sort()
    #커봤자 e 는 최소 곱하기 n
    e = times[0] * n
    s = 0
    while s<=e: 
        m = (s+e)//2
        #중간값 m
        S = 0
        #S는 m안에 몇명이 들어가는지
        piv = int(1e9)
        #piv는 나머지중에 가장 작은애(아래서 설명)
        for time in times:
            S +=  m//time
            #포문을돌면서 m이 정답이라고 가정했을때 해당심사관이 몇명을 처리했는지 더해줌
            if m%time <piv:
                piv = m%time
                """
                piv는 포문을 돌면서 나머지중에 가장 작은애
                예를 들면 문제에서 정답이 28일때 7,10,14,20,21,28로 6번째 사람이 딱 들어오면서
                끝남 근데 만약에 m이 29라고 하면 piv는 1이 남게됨, 그럼 1만큼 더 작아도 
                정답이므로(1만큼 더 작아도 S는 변하지 않음 만약에 딱 나눠 떨어지면 0이되겠져
                
                어 근데 님 m에서 piv만큼 빼다가 S가 달라지면 어카져 ? 29에서 2만큼 빼서 27이되면
                7로나눈게 4가 아니라 3이 되잖아여 >>> 애초에 m을 time으로 나눈 나머지들 중 최소
                이기 때문에 그만큼 빼도 몫이 달라질 일이 없음 
                """
        if S == n:
            return m-piv
            """
            그래서 각 심사관이 처리한 인원들을 다 더했는데 n과 같다면
            우리가 오바해서 센 piv만큼 빼주는것이 답
            """
        #아래는 그냥 이분탐색
        elif S>=n:
            e=m-1
        else:
            s=m+1
    return s

'나의 풀이'에서의 그리디 접근 방식, 사람의 수(n)과 입국심사대별 소요 시간(times)에 따른 최소 시간을 구하는 것이 아니라 시간에 따른 심사 완료 사람의 수를 이분탐색으로 구하는 것이 해답이였습니다.🐰🐰🐰

문제에서 주어진 시간의 범위를 보면 1~1,000,000,000 였고 제한 시간 내에 구현하기 위해서는 시간의 범위를 이분탐색하는 것이 열쇠였습니다.

입국 심사대별 소요시간(times) for문을 돌며 시간에 따른 심사 완료 사람수를 판별하고 주어진 사람 수(n)을 심사 완료했을 때의 최소 시간을 반환할 수 있었습니다.

또한 다음 사람이 가장 빠른 입국 심사대에서 심사받는 포인트는 따로 조건문 없이 입국 심사대별 소요 시간별(times) 공배수 즉, 심사 완료시간에 도달하는 숫자만 판단하면 되는 요소였고 문제에서 '20분이 되었을 때, 두 번째 심사대가 비지만 6번째 사람이 그곳에서 심사를 받지 않고 1분을 더 기다린 후에 첫 번째 심사대에서 심사를 받으면 28분에 모든 사람의 심사가 끝납니다.' 의 표현을 너무 어렵게 생각한 것이 원인이였습니다.

이분 탐색에 대한 개념을 잘 알고 있지만 시간의 범위를 탐색하는 아이디어를 떠올리지 못해 해결하지 못한 문제였습니다.

[다른 사람의 풀이2]

def solution(n, times):
    answer = 0
    start, end, mid = 1, times[-1] * n, 0

    while start < end:
        mid = (start + end) // 2
        total = 0
        for time in times:
            total += mid // time

        if total >= n:
            end = mid
        else:
            start = mid + 1
    answer = start
    return answer
    

'다른 사람의 풀이2'와 같은 방식입니다. 해당 문제는 이분탐생 이외에 다른 구현 방식은 없었습니다.🐱🐱🐱

감사합니다.