알고리즘 마지막 날! 시간을 쪼갤 수 있음을 배웠다!
두번째 문제는 사고의 전환을 도와준 고마운 문제였다. 알고리즘 안녕!
https://programmers.co.kr/learn/courses/30/lessons/43238?language=python3
역시 프로그래머스 문제!
n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.
처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.
모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.
입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.
입출력 예 설명
가장 첫 두 사람은 바로 심사를 받으러 갑니다.
7분이 되었을 때, 첫 번째 심사대가 비고 3번째 사람이 심사를 받습니다.
10분이 되었을 때, 두 번째 심사대가 비고 4번째 사람이 심사를 받습니다.
14분이 되었을 때, 첫 번째 심사대가 비고 5번째 사람이 심사를 받습니다.
20분이 되었을 때, 두 번째 심사대가 비지만 6번째 사람이 그곳에서 심사를 받지 않고 1분을 더 기다린 후에 첫 번째 심사대에서 심사를 받으면 28분에 모든 사람의 심사가 끝납니다.
문제 이해...
문제를 간신히 이해하고 1시간 고민... 바로 앞에 삼각형 문제를 봐서 그런가 왠지 dp로 풀어야만 할 것 같고 막 그랬다. 근데 시간이라는 개념을 대체 어떻게 여기에 우겨넣어야 하는지 생각이 나지 않았다.
그래서 정답을 검색해봤다!
정답을 보진 않더라도 제목에 접근방법이 써있어서 힌트를 얻을 때 좋기 때문이다.
근데 분야가 이진탐색이었다. 심사대 간 간격을 늘리는건가?? 하면서 한 30분 더 열심히 풀어봤지만 안되어서 다시 정답을 찾아서 클릭해보았다. 모든 정답들의 접근법은 아주 기본적인 이진탐색 형태로 변수 이름만 빼고는 전부 같았다.
즉 이 문제는 기본적인 형태의 예제 문제라는 뜻!
한번도 생각해본적 없는 개념을 금방 떠올리지 못하는 게 당연하니까 괜찮다.
그래서 배우는 자세로 돌아가서 열심히 분석했는데, 마지막까지 발상의 전환을 확실하게 체험하고 가는 기분이었다. 이 한달 동안 매일매일이 새로웠는데도 아직도 놀랄게 많이 남았다는 사실이 뭔가 기뻤다.
풀이
def solution(n, times):
answer = 0
# right는 가장 비효율적으로 심사했을 때 걸리는 시간!
left, right = 0, max(times) * n
while left <= right: # 범위가 좁혀질때까지
mid = (left + right) // 2
count = 0
for t in times: # while문 안에 2칸짜리 for문을 돌려준다
count += mid // t # mid시간동안 times[i]를 통과할 수 있는 사람의 수
if count >= n: # 카운트가 n을 넘으면 바로 브레이크
break
if count >= n: # 최소값을 구하는 문제이므로 while을 다시 돌려줌
answer = mid # 정답일수도 있으니까 현재 mid값을 정답에 저장
right = mid - 1 # 범위를 절반으로 줄여 다시 탐색
elif count < n: # 반복문을 다돌았는데 통과한 사람이 n보다 적으면 범위를 늘린다.
left = mid + 1
return answer핵심 1 : 이진탐색의 범위 정하기
이때까지 이진탐색의 범위가 될 수 있는건 거리라고 생각했지만 이 문제는 그 개념을 시간으로도 확장시킬 수 있다는 것을 보여주는 문제다. 단, 여기서 시간은 고정되어 있지 않은 요소이므로 최악을 고려하여 배치해야 한다.
예를 들면, right 값은 가장 비효율적으로 심사했을 때 걸리는 시간을 표현하기 위해 max(times) * n을 사용했는데 실제로는 한번에 2명씩 들어가기 때문에 n이 1이 아니라면 거의 대부분의 심사는 right의 시간만큼 걸릴 일이 없다. (하지만 n이 1일 가능성엔 항상 대비해야지)
left는 단순히 mid값을 잡기 위해 부여되는 변수로 left 값이 올라갈 수록 mid값이 커진다.
핵심 2 : 이진탐색의 공식
범위를 잘 정했으면 나머지는 그냥 공식이다.
while문을 범위가 좁혀질때까지 계속 돌리고 그 안에 예제였던 두배열의 교집합처럼 매개변수(times)를 범위로 하는 포문을 돌린다. 싸이클 중 목표가 매개변수(n)에 도달하면 멈추고 범위를 한번 줄여본다음 제출!
도달하지 못하면 범위를 늘려 우측에 mid를 잡고 다시 검색한다.
통과못하면 기다려야 한다던가 기다렸다가 해야한다던가 하는 예외들은 결국 최악 중의 최소시간이라는 명제 앞에서 무의미해진다. 가능한 최대거리의 최소값과 같은 말이다.
시간복잡도를 계산할 때 제곱이랑 뒤에 붙은거랑 다 생략해버리는 것처럼 아주 먼 곳에서 보면 이거나 저거나 그거나 같은 문제가 되어버리는 그런 원리이다!
끝!
알고리즘 4주 모두 수고하셨습니다.
