프로그래머스 level3 [입국심사] 파이썬

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

코딩테스트 연습 - 입국심사

def solution(n, times):
    answer = 0
    start = 1
    end = max(times)*n
    while True:
        mid = (start+end)//2
        cnt = 0
        for time in times:
            cnt += mid//time
        if cnt == n:
            end = mid
            start = mid//2
            while True:
                mid = (start+end)//2
                if start == mid or end == mid:
                    break
                cnt = 0
                for time in times:
                    cnt += mid//time
                if cnt < n:
                    start = mid
                else:
                    end = mid
            break
        elif cnt > n:
            if cnt//n >= 2:
                end = (end//(cnt//n))
            else:
                end = mid
        elif cnt < n:
            if n//cnt >= 2:
                start = (start*(n//cnt))
            else:
                start = mid
    answer = mid+1
    return answer

위의 코드는 내가 실패한 코드이다.

이분 탐색을 실행하였지만, for문을 끝까지 돌기 때문에 시간 초과가 발생한다.

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

다른 분들의 풀이를 참고하여 다시 작성한 코드이다, 위의 코드에서는 for문 도중에 조건을 만족하면 break 을 실행하기 때문에 시간초과가 발생하지 않는다.

 

이분탐색에 대해서 어렴풋이 알고있었던것 같다. 더 많은 문제를 풀어보면서 감을 익혀야겠다..