[프로그래머스💯] 코딩테스트 연습 > 이분탐색 > 입국심사 / Python 문제풀이

<프로그래머스 문제풀이>

<출처 : 프로그래머스(Programmers)>

 

---

해답)

 

def solution(n, times):
    times.sort()
    start = times[0] * n / len(times)
    end = times[len(times)-1] * n / len(times)

    def find(s, e):
        if s == e:
            return s
        mid = int((s+e)/2)
        nSum = 0
        for time in times:
            nSum += mid//time
            if nSum > n:
                break
        if nSum >= n:
            return find(s, mid)
        else:
            return find(mid+1, e)

    answer = find(start, end)
    return answer

 

풀이)

0. 우리가 구하고자 하는 것 : 모든 사람이 심사를 받는데 걸리는 시간

 

1. 답의 범위를 좁혀준다.

모든 심사원의 일처리 속도를 일처리가 제일 빠른 심사원 값 으로 한 것보단 클 것이고 

모든 심사원의 일처리 속도를 일처리가 제일 느린 심사원 값 으로 한 것보단 작을 것이다.

 

2. 이분 탐색을 이용해 답의 범위 안에서 만족하는 최소값을 구해낸다.

( nSum> n 이 아닌 nSum >= n ) 이기 때문에 nSum == n 이었을 때도 아래의 값을 보게 되어 최솟값을 구할 수 있다.

 

* 이 문제 및 로고의 저작권은 Programmers에 있습니다.

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges