코딩테스트 연습 - 입국심사(이분탐색) trying...

[문제]

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분에 모든 사람의 심사가 끝납니다.

---

[풀이]

(1) 첫번째 시도 - 일부 성공, 일부 실패, 절반 이상의 시간초과.

	타임라인
1번 심사대(7)	7분		14분		21분	28분
2번 심사대(10)		10분		20분

각 심사대마다 입국 심사에 걸리는 시간이 다를 때 n명이 모두 심사를 받기위한 최소한의 시간을 구해야하는 문제다.

처음에는 테스트 케이스만 보고 쉽게 풀 수 있을거라고 생각했던게 오산이었다. 

 

나올 수 있는 타임라인을 모두 구한 뒤 거기서 n번째 타임을 구하면 쉽게 최소 시간이 도출 되었다. 

예를 들어서 7분이 걸리는 1번 심사대에서 6명이 모두 받으려면 [7분, 14분, 21분, 28분, 35분, 42분]이 걸리고 2번 심사대에서는 [10분, 20분, 30분, 40분, 50분, 60분]이 걸린다. 이걸 합쳐주고 오름차순으로 정렬해주면 [7, 10, 14, 20, 21, 28, 30, 35, 40, 42, 50, 60]이 되고 이 중에 6번째인 28이 최소 시간이 된다.

 

당연히 이 방법으로 손쉽게 테스트 케이스를 성공했고 제출버튼을 눌렀다.

일부성공과 일부 실패 그리고 거의 대부분이 시간 초과에 걸렸다. 

왜 시간초과일까를 생각해보았는데 타임라인을 모두 구하는 방법에서부터가 문제였다. 

 

나는 for문을 사용해서 각 times의 원소에 1~n까지를 곱한 값을 타임라인이라는 리스트에 담고 혹시 중복된 값이 있을 수 있기에 set으로 중복을 제거해준뒤 다시 오름차순으로 정렬해주는 방법을 통해 타임라인 리스트를 뽑아냈다.

 

하지만 이 방법을 사용할 때 만약 n이 최대인 10억명이라고 하면 1부터 10억까지를 모두 곱해줘야하는 일이 발생했다.

 

그렇다면 시간초과는 이해가 되는데 실패는 뭐였을까.

 

몇가지 테스트 케이스를 떠올려보다가 배수 때문이겠다는 생각이 들었다.

 

예를 들어서 7명이 심사를 기다리고 있고 심사대가 각각 3, 6, 9분이 걸린다고 했을 때, 내가 생각했던 방법대로 타임라인리스트를 만들면 21분이 걸리게 된다. 하지만 실제로는 12분이면 7명이 모두 심사를 받을 수 있다. 

 

이해하기 쉽도록 표로 보자.

	타임라인
1번(3분)	3	6	9	12	15	18	21
2번(6분)		6		12		18
3번(9분)			9

표를 보면 알 수 있듯이 원래대로라면 12분동안 1번 심사대에서 4명, 2번 심사대에서 2명, 3번 심사대에서 1명이 심사를 마칠 수 있다. 하지만 나는 중복값을 제거해주느라 1번 심사대에서만 7명이 받아야 끝나게 된다.

 

(2) 두번째 시도 - 일부 성공, 여전히 절반 이상의 시간초과

그래서 다시 생각한 방법은 딕셔너리를 이용해주는 방법이었다. 

타임라인과 심사대에서 걸리는 시간이 일치하거나 배수일때마다 카운트를 해주고 그 카운트한 값을 키로 딕셔너리에 타임라인값을 넣어주었다.

예를 들어서 dic[1] = 3, dic[2] = 6, dic[3] = 6, dic[4] = 9, dic[5] = 9, dic[6] = 12, dic[7] = 12 처럼 해주면 dic[n]값을 불러오면 최소 시간을 구할 수 있었다.

def solution(n, times):
    times = sorted(times)
    timeline = []
    count = 0
    dic = {}
    
    for i in times:
        for j in range(1, n):
            timeline.append(i*j)
    
    timeline = sorted(list(set(timeline)))
    
    for i in timeline:
        for j in times:
            if i % j == 0:
                count += 1
                dic[count] = i
            
    
    return dic[n]

이 방법으로 다시 제출을 해보았지만 일부 실패로 뜨던 문제들은 해결 했지만 아직 시간문제는 해결하지 못했기에 절반이상은 여전히 시간 초과로 남아 있었다. 

 

(3) 세번째 시도 - 진행 중

 

그래서 드는 생각은 타임라인을 먼저 만들고 거기에 걸리는 심사대를 카운팅 하는 방법을 버리고 카운팅과 동시에 타임라인을 만들어가야겠다는 생각이 들었다. 아직까지 구체적으로 어떻게 해야할지는 떠오르지 않지만 해결되면 포스팅을 수정하도록 하겠다.