[프로그래머스] 입국심사(Level 3)

문제 설명

 

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

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

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

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

제한사항

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

입출력 예

n	time	return
6	[7, 10]	28

입출력 예 설명

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

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

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

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

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

출처

※ 공지 - 2019년 9월 4일 문제에 새로운 테스트 케이스를 추가하였습니다. 도움을 주신 weaver9651 님께 감사드립니다.

 

풀이

import numpy as np

def solution(n, times):
    
    times.sort()
    immi = [[] for i in range(len(times))]

    for i in range(len(times)):
        immi[i] = [times[i], 0, 0]

    #가능한 최대 시간
    max = times[-1] * n
    for i in range(max):
        chk = 0
        for j in range(len(times)):
            #시간을 다 채운 후 심사대 비우기, 시간 증가
            if (immi[j][0]-1) == immi[j][1]:
                immi[j][1], immi[j][2] = 0, 0
            elif immi[j][2] == 1:
                immi[j][1] += 1
            #심사할 사람이 남아 있고 심사대가 비어있을 때
            if n!=0 and immi[j][1]==0:
                n -= 1
                immi[j][2] = 1
            chk += immi[j][2]

        if n==0 and chk==0:
            return i
            
    return max

처음에는 이런식으로 반복문을 통해 1분씩 증가해가면서 심사 시간, 지금 심사하고 있는 시간, 현재 심사대에 사람이 있는지 여부를 배열에 넣고 하나씩 계산해보려고 했는데 이러면 마지막에 가장 적은 시간이 나오는 심사대를 고르는 과정이 복잡해져서 다른 아이디어를 생각했다.

 

예를 들어서 times배열이 [4, 5, 10, 13]이고 11명의 사람이 심사받는다고 가정해보자.

이런식으로 총 20분이 걸린다. 이 때, 4번은 4명, 5번은 4명, 10번은 2명, 13번은 1명의 사람을 심사할 수 있다. 이 값을 가지고 시간을 계산해주면 된다.

 

20분 동안 심사한다고 했을 때, 4번은 5명, 5번은 4명, 10번은 2명, 13번은 1명의 사람을 심사할 수 있으므로 총 12명의 사람을 심사할 수 있다. 19분 동안 심사한다고 가정해보자. 4번은 4명, 5번은 3명, 10번은 1명, 13번은 1명으로 총 9명의 사람을 심사할 수 있게 된다. 이때는 11명보다 적기 때문에 틀린 값이 된다. 즉, 11명 이상 검사할 수 있는 시간 중 가장 작은 값을 찾으면 된다.

 

import numpy as np

def solution(n, times):
    times.sort()
    times = np.array(times)
    left, right = 0, times[-1]*n

    while(left < right):
        mid = (left+right)//2
        if sum(mid//times) <= n:
            left = mid+1
        else:
            right = mid-1

    return mid

 

이런식으로 numpy를 써서 푸니까 "TypeError: Object of thpe int64 is not JSON serialliszble" 이런 에러가 발생한다. times배열에 1,000,000,000까지 들어올 수 있으니까 int64형이 numpy 배열에 들어오고 계산되는 과정에서 오류가 발생한 것 같아서 그냥 리스트 그대로 계산해주었다.

추가로 left와 right가 똑같을 때, 조건을 만족한다면 그대로 mid를 return하지만 조건을 만족하지 않으면 mid+1을 return해주는 조건까지 추가해주면 풀린다.

 

def solution(n, times):
    times.sort()
    left, right = 0, times[-1]*n

    while(left <= right):
        mid, sum = (left+right)//2, 0

        for i in times:
            sum += mid//i

        if sum >= n:
            right = mid-1
        else:
            if left==right:
                return mid+1
            left = mid+1

    return mid

테스트 1 〉	통과 (0.02ms, 10.2MB)
테스트 2 〉	통과 (1.16ms, 10.2MB)
테스트 3 〉	통과 (4.41ms, 10.3MB)
테스트 4 〉	통과 (413.86ms, 14.4MB)
테스트 5 〉	통과 (716.05ms, 14.4MB)
테스트 6 〉	통과 (676.49ms, 14.4MB)
테스트 7 〉	통과 (1081.79ms, 14.4MB)
테스트 8 〉	통과 (1625.40ms, 14.4MB)
테스트 9 〉	통과 (0.06ms, 10.1MB)