처리해야 할 동일한 작업이 n 개가 있고, 이를 처리하기 위한 CPU가 있습니다.
이 CPU는 다음과 같은 특징이 있습니다.
CPU에는 여러 개의 코어가 있고, 코어별로 한 작업을 처리하는 시간이 다릅니다.
한 코어에서 작업이 끝나면 작업이 없는 코어가 바로 다음 작업을 수행합니다.
2개 이상의 코어가 남을 경우 앞의 코어부터 작업을 처리 합니다.
처리해야 될 작업의 개수 n과, 각 코어의 처리시간이 담긴 배열 cores 가 매개변수로 주어질 때, 마지막 작업을 처리하는 코어의 번호를 return 하는 solution 함수를 완성해주세요.
이분 탐색을 사용해서 풀어야 하는 생각이 들었지만, 어떤 기준을 정하고 풀어야 하는지 감이 잡히지 않아서 꽤나 고생한 문제다.
1.만약 n값이 cores의 길이보다 작을 경우, n값이 곧 정답이다.
시작과 동시에 모든 cpu에 차례로 작업이 하나씩 시작되므로, 앞에서부터 n번째 cpu가 마지막 작업을 처리하게 될 cpu이다.
ex) n = 4, cores = [1,2,3,4,5,6,7] -> answer = 4
2.이분탐색을 진행
left, right, mid 값은 시간값이 될 것이며, n과 비교할 것은 n-1 시간동안 처리된 작업의 양
이다.
n = 10, cores = [1,2,3,4] 의 예시가 있을 때 다음과 같은 규칙으로 매 시간마다 작업이 진행된다.
따라서 어떤 시간 h에 대해, 진행된 총 작업 수 = 시작(0h)에 진행된 작업 수 + 매 시간(h)에 대해 새로 추가되는 작업 수
이다. 이를 이용해 시간 h일 때 진행된 총 작업 수를 구할 수 있다.
이분탐색을 통해 left, right 값을 이용해서 mid의 값을 얻을 것인데, 위에서 말했듯 이 값들은 시간(h) 이다. 즉, left = min(cores) * n // len(cores)
, right = min(cores) * n
에서 시작해서, mid = left + right // 2
로 계산해나가며, mid시간의 총 작업수가 타겟 작업수인 n 보다 크거나 같은 지점을 찾는 것이다.
여기서 배열내에 있는 값이 아닌 'n보다 큰 값 중 가장 작은 값'을 구하는 것이기 때문에, 이분탐색에서도 lower bound 알고리즘이라고 볼 수 있다.
3.반복문을 통해 몇 번째 cpu가 마지막이 될 것인지 확인
찾아낸 (h-1)
까지의 총 작업수를 n에서 뺀다. 그러면 남아있는 작업 수는 전부 현재 시간(h) 안에서만 이루어졌다는 것이다.
n = 10, cores = [1,2,3,4]
의 예시에서, 정답은 4h의 1번 cpu다.
3h까지의 작업 수가 9이므로, n - (h-1 까지의 총 작업 수) = 1
, 즉 한 개의 작업만 더 실행하면 된다.
따라서, 4h에서 진행 가능한 cpu 중 가장 앞에 있는 cpu인 1이 정답이 되는 것이다.
즉, h - 1시간까지의 총 작업량
을 구한 뒤에, h시간의 cpu를 하나씩 진행가능한 상태인지 count하며 n의 값이 채워지면, 그것이 정답이 되는 것이다.
만약 n = 12
라면, 3h까지 9개의 작업을 진행하고 나서 3개의 작업이 더 필요하니, 4h의 작업가능한 세번째 cpu, 4번 cpu가 정답이 되는 것이다.
# 파라메트릭 서치
def solution(n, cores):
if n <= len(cores):
return n
n -= len(cores)
# 마지막 작업이 실행되는 시간을 찾아내는 이분탐색 실시
left = min(cores) * n // len(cores)
right = min(cores) * n
while left < right:
mid = (left + right) // 2
_sum = 0
for core in cores:
_sum += mid // core
if _sum >= n:
right = mid
else:
left = mid + 1
# 결과로 나온 rignt = 마지막 작업이 코어에 들어가는 시간.
# 이제부터 해당 시간에 어떤 코어로 작업이 들어가는지 알아내야한다.
for core in cores:
n -= (right-1) // croe
for i in range(len(cores)):
if right % cores[i] == 0:
n -= 1
if n == 0:
return i + 1
참고 : 개발하는 사막여우