[프로그래머스] 이분탐색 / 입국심사

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

 

문제 요약

 

목표: 총 심사 시간 최소화.

 

Input

n: 입국 심사 기다리는 사람 수 (엄~~~~청 큼.)

Times: ‘각 심사관이 한 명을 심사하는 데 걸리는 시간’이 담긴 배열 (각 시간이 엄청 큼) (사람 수는 10만.)

e.g) 6, [7,10]

 

Return

심사 총 시간.

e.g) 28

 

한 심사대 - 한 명

가장 앞에 있는 사람: 비어 있는 심사대에서 심사 받기.

더 빨리 끝나는 심사대 있으면: 기다렸다가 그곳에서 심사 받기.

*20분이 되었을 때, 두 번째 심사대가 비지만 6번째 사람이 그곳에서 심사를 받지 않고 1분을 더 기다린 후에 첫 번째 심사대에서 심사를 받으면 28분에 모든 사람의 심사가 끝납니다.

 

예제

 

(7) 끝난 사람 1

(10) 끝난 사람 2

(14) 끝난 사람 3

(20) 끝난 사람 4

(21) 끝난 사람 5

(28) 끝난 사람 6

(30) 끝난 사람 6

 

정답은 각 시간의 배수 중 하나.

• 7 (<=7*1, 10*0) : 1
• 14 (<=7*2, 10*1) : 3
• 21 (<=7*3, 10*2): 5
• 28 (<=7*4, 10*2): 6

 

• 10 (<=10*1, 7*1) : 2
• 20 (<=10*2, 7*2) : 4
• 30 (<=10*3, 7*4) : 7 (6)
• 40 (<=10*4, 7*5) : 9 (6)

times의 각 원소의 배수들을 모두 나열.

각 배수를 우측의 부등호처럼 표현하고 곱한 수의 합이 n이상인 경우 중

가장 작은 배수값을 찾아냄.

이때 합이 n이상이면 max(합, n)으로 간주.

 

28 // 7 = 4

28 // 10 = 2

 

---

내 코드

 

def solution(n, times):
    
    times.sort()
    start = times[0]
    end = times[0]*n
    cand = end #candidate: 정답 후보
    
    while start <= end: #이분탐색은 start, end를 지정해주어야 함
        mid = (start+end) // 2 #start, end를 바탕으로 mid 생성

        if sum([mid//i for i in times]) < n:
            start = mid + 1
        elif sum([mid//i for i in times]) > n:
            cand = mid
            end = mid - 1
        else:
            if start==end: #해당 조건 없으면 무한루프
                return start
            cand = mid
            end = mid
    
    #반복문 종료되었을 때, 반복문의 최종 candidate값으로 정답을 반환
    
    return cand