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

Level 3 → 이분 탐색

 

문제 설명

n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.

처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.

모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.

입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
• 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
• 심사관은 1명 이상 100,000명 이하입니다.

입출력 예

n	times	return
6	[7, 10]	28

---

나의 Solution <Python>

def solution(n, times):
    answer = 0
	
    times.sort()
    low = 1 # 최소 시간 → 1분
    high = int(times[len(times) - 1] * n) # n명의 사람이 입국 심사하는 데 걸리는 최대 시간 → 60분

    while low < high:
        ppl = 0 # mid분 동안 입국 심사 완료한 사람의 수
        mid = int((low + high) / 2) # 모든 사람 입국 심사 소요 시간

        for i in range(len(times)):
            ppl += int (mid / times[i]) # mid분 동안 i번째 gate 입국 심사 가능한 사람 수

        if ppl >= n: # n명보다 많이 입국 심사 통과
            high = mid # decrease mid
        else: # n명 통과X (less than n)
            low = mid + 1 # increase mid

    answer = high

    return answer

low, mid, high => 입국 심사에 소요된 총 시간

---

디버깅

n = 6명의 사람들

1

2

3

4

5

6

times = 입국 심사대(소요 시간)

7

10

low = 1
high = (2 - 1) * 6 = 60

while 1 < 60:
(low = 1, high = 60)
mid = (1 + 60) / 2 = 30

ppl = (30 / 7) + (30 / 10) = 7
7 >= 6 → high = 30

while 1 < 30:
(low = 1, high = 30)
mid = (1 + 30) / 2 = 15

ppl = (15 / 7) + (15 / 10) = 3
3 < 6 → low = 15 + 1 = 16

while 16 < 30:
(low = 16, high = 30)
mid = (16 + 30) / 2 = 23

ppl = (23 / 7) + (23 / 10) = 5
5 < 6 → low = 23 + 1 = 24

while 24 < 30:
(low = 24, high = 30)
mid = (24 + 30) / 2 = 27

ppl = (27 / 7) + (27 / 10) = 5
5 < 6 → low = 27 + 1 = 28

while 28 < 30:
(low = 28, high = 30)
mid = (28 + 30) / 2 = 29

ppl = (29 / 7) + (29 / 10) = 6
6 >=  6 → high = 29

while 28 < 29:
(low = 28, high = 29)
mid = (28 + 29) / 2 = 28

ppl = (28 / 7) + (28 / 10) = 6
6 >= 6 → high = 28

while 28 == 28: break

answer = 28 (high)