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

 

programmers.co.kr/learn/courses/30/lessons/43238#

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

문제 설명

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

입출력 예 설명

가장 첫 두 사람은 바로 심사를 받으러 갑니다.

7분이 되었을 때, 첫 번째 심사대가 비고 3번째 사람이 심사를 받습니다.

10분이 되었을 때, 두 번째 심사대가 비고 4번째 사람이 심사를 받습니다.

14분이 되었을 때, 첫 번째 심사대가 비고 5번째 사람이 심사를 받습니다.

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

풀이

이분탐색이라는 분류가 붙지 않았더라면 풀지 못했을 문제. 아니 처음에는 실제로 이분탐색을 어디 써먹지? 하며 풀지 못했습니다.

def solution(n, times):
    answer = []
    for time in times:
        for i in range(n):
            answer.append(time * (i+1))
    return sorted(answer)[n-1]

테스트케이스도 빈약하고 생각나는대로 손이 움직이다보니 다음과 같이 O(mn log mn), m = len of times의 시간복잡도로 제출했고, 아래와 같은 결과가 나왔습니다. 테스트 8은 보나마나 시간 초과겠죠?

먼저, 위 방법은 "사람"을 기준으로 생각했을 때 나오는 답안입니다. n번째 사람을 체크하는 게 목적이라고 생각했으니까요. 그래서 가능한 시간대를 모두 만들고 정렬해서 n번째 사람의 시간을 뽑아낸 것입니다.

기준을 "시간"으로 달리 생각해봅시다. 1, 2, 4분 만에 통과할 수 있는 사람은 0명, 8분 1명, 16분 3명, 32분 7명. 여기까지 확인하면 6번째 사람의 심사가 끝나는 시간은 16분과 32분 사이일 것이라는 생각이 듭니다. 표로 정리해봅시다.

total time	diff	count
1	-	0
2	+ 1	0
4	+ 2	0
8	+ 4	1+0=1
16	+ 8	2+1=3
32	+ 16	4+3 >= 6
24	- 8	3+2=5
28	+ 4	4+2=6 >= 6
26	- 2	3+2=5
27	+ 1	3+2=5

이렇게 하면 보다 빠르게 확인할 수 있습니다.

다른 케이스를 생각해봅시다.

n	times	return
10	[5, 7, 10, 15]	21

 

total time	diff	count
1	-	0+0+0+0=0
2	+ 1	0+0+0+0=0
4	+ 2	0+0+0+0=0
8	+ 4	1+1+0+0=2
16	+ 8	3+2+1+1=7
32	+ 16	6+4+3+2=15 >= 10
24	- 8	4+3+2+1=10 >= 10
20	- 4	4+2+2+1=9
22	+ 2	4+3+2+1=10 >= 10
21	- 1	4+3+2+1=10

 

 

 

n	times	return
16	[5, 7]	49

total time	diff	count
1	-	0+0=0
2	+ 1	0+0=0
4	+ 2	0+0=0
8	+ 4	1+1=2
16	+ 8	3+2=5
32	+ 16	6+4=10
64	+ 32	12+9=21 >= 16
48	- 16	9+6=15
56	+ 8	11+8=19 >= 16
52	- 4	10+7=17 >= 16
50	- 2	10+7=17 >= 16
49	- 1	9+7=16

total time += diff 식으로 변화하고, diff의 절댓값은 2배씩 증가하다 count가 n을 넘어서는 순간부터 2배씩 감소합니다. diff의 부호는 이전 루프에 count가 n보다 크거나 같았는지 여부에 따라 결정됩니다. 이를 코드로 나타내봅시다.

def solution(n, times):
    answer = -1
    totalTime = 1; sign = 1; time = 0
    isOnceOver = True
    
    while isOnceOver or time > 0:
        totalTime += sign * time
        count = sum([totalTime // t for t in times])

        if count >= n and (answer == -1 or answer > totalTime):
            answer = totalTime
        if count < n:
            sign = 1
        else:
            isOnceOver = False
            sign = -1
            
        if time == 0:
            time = 1
        elif isOnceOver:
            time *= 2
        else:
            time //= 2
    
    return answer

기다리는 사람은 1명 이상, 검사에 걸리는 시간도 1분 이상이기 때문에 totalTime은 최소 1입니다.

증감값인 time은 최초 0이며, 부호 sign은 양수(= 1)입니다.

count가 n을 넘어섰는지 체크하는 flag 변수 isOnceOver은 True로 초기화합니다.

루프문은 count가 n을 넘어선 적이 있고, 증감값이 더이상 변화하지 않을 때 종료됩니다.

count는 totalTime 안에 전체 검사관이 몇 명을 검사할 수 있는지 나타낸 변수로, 대상이 사람이기 때문에 몫만 구해 더해줍니다.

주어진 시간 동안 주어진 수의 사람과 같거나 보다 많은 사람을 검사할 수 있는 경우, 해당 주어진 시간은 정답 후보군에 들어갑니다. 그보다 작은 시간 안에 같은 수의 사람을 검사하는 경우가 있기 때문입니다.

케이스에 따라 시간 변화량을 설정해줍니다.

보다 간결하지만 복잡한 코드

MAX = 60

def solution(n, times):
    base = 0
    for i in range(1, MAX + 1):
        totalTime = base + 2 ** (MAX - i)
        if sum([totalTime // time for time in times]) < n:
            base = totalTime
            continue
            
        if sum([(totalTime-1) // time for time in times]) < n:
            return totalTime
    return totalTime

 

다른 사람의 풀이를 정리한 코드입니다. 비슷한 논리를 채택했지만 위에서부터 내려오기 때문에 2 ** (MAX - i) 값은 항상 작아지며 부호나 flag를 위한 변수를 작성할 필요가 없습니다. 또한, 정답 후보군에 대해서는 totalTime-1의 count를 바로 확인하여 판별하는 것을 볼 수 있습니다.

다만 찜찜한 것은, MAX = 60의 존재입니다. 위에서부터 내려오는 방법을 채택하려면 먼저 상한선을 알아야하고, 입국심사 대기자는 1명 ~ 10억 명, 심사관이 심사에 걸리는 시간도 1분 ~ 10억 분 이하이므로 최대로 커버해야 하는 값은 10^18입니다. 따라서 MAX를 60으로 잡을 수 있고, 확정적으로 루프를 60번 돌면 값을 구할 수 있으나... 위에서부터 내려온다는 발상을 떠올리기 쉽지 않은 것 같습니다.