1. 오늘의 문제
사실 처음에 이진탐색이라는 힌트를 보고 조금 실망했다.
"또 이진 탐색이야?"
하지만 30분이 지나도록 어떻게 풀어야 할지 감이 잡히지 않았다.
그래서 나에게 실망하는 시간이었다.
문제 설명
n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.
처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.
모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.
입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.
2. 원리
결국 다른 분들이 티스토리에 올린 글들의 힌트를 참고했다.
힌트는 어떤 시간이 주어졌을 때, 그 시간에 통과한 사람들이 얼마인지를 합산하면 된다는 것.
예를들어 인원이 n = 6, times = [7, 10]이라고 주어졌다면 최대시간에서 최소시간으로 가면서 통과한 사람의 수를 센다.
임의로 시간의 최소값은 0, 최대값은 times를 sort 한 뒤 times[-1]값에 인원수를 곱했다.
이제 이 값으로 이진 탐색을 한다.
- 0과 42의 중간값인 21을 중간값으로 잡는다.
- 그리고 21을 7로 나눈 몫과 10으로 나눈 몫을 합한다. 이 상황에서 합은 5이다.
- 그럼 인원수인 n보다 작다.
- 그러므로 시간의 최소값을 21, 최대값을 42로 다시 설정한다.
- 이 과정을 반복한다.
그럼 결국에 모든 사람이 통과할 수 있는 최소 시간이 나온다.
3. 코드
def solution(n, times):
# 심사관이 1명이라면 탐색할 필요가 없다.
if len(times) == 1:
answer = times[0]*n
return answer
# 심사관의 심사 시간을 정렬한 뒤, 최대 시간과 최소 시간을 정한다.
times.sort()
minTime = 0
maxTime = times[-1]*n
# while문을 돌면서 이진 탐색을 한다.
while minTime<maxTime:
midTime = (maxTime+minTime)//2
# 해당 시간에 통과한 사람수를 구한다.
totalPass = 0
for i in times:
totalPass += midTime//i
if minTime == maxTime:
break
# 만일 통과한 사람의 수가 인원보다 적으면 중앙값을 최솟값으로 재설정
if totalPass < n:
minTime = midTime+1
# 그게 아니라면 중앙값을 최댓값으로 재설정
else:
maxTime = midTime
answer = maxTime
return answer
4. 느낀점
벌써 3일째 이진 탐색을 하는데 아직도 이진 탐색을 다양한 상황에 적용하는게 쉽지 않다.
특히 이번 문제는 시간을 줄여가며 통과한 사람을 센다는 그 아이디어 자체가 중요한 핵심이었는데, 그런 사고력이 부족했던 것 같다.
조금 더 많은 문제를 접해보아야 겠다는 생각이 드는 하루였다.
