[프로그래머스] LV.4 선입 선출 스케줄링 (JS)

문제

처리해야 할 동일한 작업이 n 개가 있고, 이를 처리하기 위한 CPU가 있습니다.

이 CPU는 다음과 같은 특징이 있습니다.

• CPU에는 여러 개의 코어가 있고, 코어별로 한 작업을 처리하는 시간이 다릅니다.
• 한 코어에서 작업이 끝나면 작업이 없는 코어가 바로 다음 작업을 수행합니다.
• 2개 이상의 코어가 남을 경우 앞의 코어부터 작업을 처리 합니다.

처리해야 될 작업의 개수 n과, 각 코어의 처리시간이 담긴 배열 cores 가 매개변수로 주어질 때, 마지막 작업을 처리하는 코어의 번호를 return 하는 solution 함수를 완성해주세요.

제한

• 코어의 수는 10,000 이하 2이상 입니다.
• 코어당 작업을 처리하는 시간은 10,000이하 입니다.
• 처리해야 하는 일의 개수는 50,000개를 넘기지 않습니다.

입출력 예시

n	cores	result
6	[1,2,3]	2

풀이

선입선출(FCFS; First Come First Served) 알고리즘은 운영체제에서 프로세스 스케줄링을 다룰때 언급되는 개념이기도 하다. 가장 먼저 도착한 프로세스를 가정 먼저 서비스하는 개념으로 위에 문제 또한 이와 유사한 개념이다. 알고리즘의 영역에서는 FIFO(First In First Out)의 개념으로 더 잘 알려져 있는 것 같다. 하지만 위의 문제를 FIFO의 개념을 적용하여 순차적으로 해결하려고 할 시, 제한 조건에 의해 시간복잡도를 초과할 가능성이 높다. 따라서 효율적으로 선입선출을 적용할 수 있는 방법을 찾아보도록 하자.

1) 시간복잡도

가장 간단하게 풀이할 수 있는 방법은, 작업을 일일이 하나씩 처리하면서 for문을 도는 방법이 있다. 1부터 n까지 1씩 증가시키면서 각 코어가 이를 커버할 수 있는지 체크하면서 카운트하면, 카운트 수가 작업량과 일치하는 순간의 코어의 위치를 리턴할 수 있다. 하지만 이 방법은 당연히 시간복잡도를 통과하지 못한다.

조금 최적화 할 방법을 생각해보면 우선순위 큐(Priority Queue)를 적용해볼 수 있다. 우선순위 큐에서는 항상 작은 값을 먼저 추출할 수 있기 때문에 위에 언급한 방법보다 더 빠른 시간 안에 비교를 진행할 수 있다. 그러나 해당 문제에서는 우선순위 큐를 이용하더라도 효율성 테스트를 통과할 수 없다. 우선순위 큐가 기본 라이브러리로 제공되지 않는 자바스크립트의 입장에서는 두 손 벌려 환영(?)할 만한 소식이다.

때문에 우리는 이보다 더 빠른 시간복잡도를 가진 알고리즘을 떠올려야 한다. 물론 이 과정에 이르기까지 오랜 시행착오가 소요되었을 수 있지만, 어찌되었건 이 시점에 이르렀다고 해보자. 우리가 이제 고려해봄직한 알고리즘은 O(logN)의 시간복잡도를 가진 이분탐색 알고리즘이 있다. 따라서 이분탐색을 이용해 해당 문제에 접근해보자.

2) 이분탐색 or Parametric Search

Parametric Search는 일종의 이분탐색이다. 해당 문제에서도 해당 기법을 이용해 풀이할 것인데, 이분탐색과 크게 다르지 않다. 만약 이분탐색과 Parametric Search 간의 세세한 차이를 알고 싶다면 다른 PS전문 블로그를 참고할 것을 권한다. 간단하게만 언급하면 용어에서 알 수 있듯이 매개변수를 설정하여, 해당 값을 가지고 이분탐색을 수행하는 알고리즘이다. 사실 대부분의 이분탐색에서 매개변수 역할을 하는 mid값을 자연스레 설정하기 때문에 Parametric Search가 이분탐색의 하위집합이라고 간단하게 생각하고 넘어가도 될 것 같다.

그렇다면 어떤 값을 기준으로 이분탐색을 수행할 지 생각해보자. 즉 어떤 값을 매개변수(Parameter)로 설정할 지 생각해보아야 한다. 이 과정만 원활하게 할 수 있다면 사실 문제를 거의 풀었다고 보아도 좋다.

3) 진행된 총 작업 수

코어별로 처리하는 시간의 단위가 시간이라고 해보자. 코어가 작업을 처리하는 시간은 최소 1이상 - 최대 10,000이하이기 때문에 우리는 이를 1시간 단위로 나누어 생각해 볼 수 있다. 즉 코어가 m개 있을 때, 시간별로 처리가능한 작업량을 어떻게 구할 수 있을지 생각해보자.

문제에서 주어진 예시는 총 작업량이 6이고, 코어는 [1, 2, 3]으로 총 3개가 주어져있다. 이때 한 가지 주의해야할 점은, 초기 상태에서 모든 코어는 비워져 있다는 점이다. 즉 가장 초기 상태에서는 모든 코어가 작업을 수행하고 있지 않기 때문에, 작업 처리에 얼마나 시간이 걸리든간에 상관없이 바로 작업을 위임할 수 있다. 우리는 이를 0H(0시간)이라고 표현하자.

HOUR	Core1	Core2	Core3	진행된 작업 수
0H	✔	✔	✔	3
1H	✔			4
2H	✔	✔		6
3H	✔		✔	8
4H	✔	✔		10
5H	✔			11

✔는 코어가 비워져있기 때문에 작업이 할당되었다는 것을 의미한다. 앞서 이야기 한 바와 같이 초기 상태인 0H시점에서는 모든 코어가 비워져 있기 때문에 바로 작업을 하나씩 할당 가능하다.

Core[Number]에서 Number는 코어의 작업 시간 주기를 의미한다. 즉 Core1이라면 해당 코어는 1시간 단위로 작업을 처리한다. 때문에 Core1의 경우는 매 시간마다 새로운 작업을 할당하고 있고, Core2의 경우에는 2시간 마다 새로운 작업을 할당한다. 따라서 우리는 코어의 작업 처리 주기의 배수가 되는 시간에 새로운 작업이 추가된다는 사실을 알 수 있다. 그렇다면 어떤 시간 H가 주어졌을 때, H의 약수에 해당하는 코어 넘버만큼의 작업이 진행된 총 작업수에 추가될 것이다. 따라서 우리는 다음의 사실을 추출해낼 수 있다.

• 어떤 시간 H가 주어졌을 때, cores의 요소가 H의 약수에 해당하는 경우 해당 요소는 새로운 작업이 할당됨

즉 만약 위의 예시에서 2H가 주어진다면, 이의 약수는 1, 2가 되기 때문에 Core1과 Core2는 이 시점에서 새로운 작업을 할당할 수 있다. 따라서 이전 시간대인 1H의 작업량에 현재 추가된 작업량을 더한다면 최종적으로 어떤 시간 H가 주어졌을 때 실행된 총 작업량을 구할 수 있다.

• 어떤 시간 H가 주어졌을 때, 총 작업량의 수 = H-1의 작업량 수 + H시간에 추가된 작업량의 수

4) 매개변수 설정

그럼 다시 이분탐색으로 돌아와서 어떤 값을 기준으로 매개변수를 삼을지 생각해보자. 현재 주어져 있는 값들을 종합해보면 다음과 같다.

• 총 처리해야하는 일의 개수 n
• 코어의 개수 cores.length
• 각 코어의 처리 시간 단위 [...cores]

이들만 가지고는 무엇을 기준으로 삼아야 할 지 도통 좋은 생각이 떠오르지 않는다... 조금 생각을 전환해보자.

각 코어의 요소는 해당 코어가 작업을 처리하는데 소요되는 시간을 의미한다. 따라서 우리는 이 값을 통해 처리하는데 가장 짧은 시간이 걸리는 코어와, 가장 오랜 시간이 걸리는 코어를 구할 수 있을 것이다.

시간하니깐 다시 위에서 그렸던 표를 떠올려보자. 우리가 표를 통해 추출했던 중요한 사실 역시 시간과 관련이 있었다. 특정 시간 H가 주어졌을때 우리는 그때 처리된 작업량의 개수를 구할 수 있다는 것을 알 수 있었다. 그렇다면 시간을 기준으로 이분탐색을 진행할 수 있지 않을까?

우리가 필요한 것은 총 작업량 n이 주어졌을때, 이 n개의 작업을 처리할 수 있는 최소 시간 H를 구하는 것이다. 이때의 시간대를 구한다면 이전의 시간대 H-1에서 처리된 작업량의 개수를 구해, 마지막 작업이 몇 번째 코어에서 진행되어야 하는지 계산할 수 있을 것이다.

따라서 시간을 매개변수로 삼아 이분탐색을 진행하도록 하자. 이분탐색의 조건을 이 값이 충족하는지 검증이 필요하다. 앞서 이야기 한 것과 같이 min/max값을 설정할 수 있기 때문에 충분히 성립할 수 있음을 알 수 있다. 따라서 최소값과 최대값을 다음과 같이 구해주도록 하자. 여기서는 최소/최대값이라고 표현했지만 이분탐색에 맞게 최소값을 left, 최대값을 right라고 표현하겠다. (min/max라고 해도 뭐 상관은 없다. 개취존중!)

const len = cores.length;

let left = 1;
let right = Math.max(...cores) * rest / len;

이때 left와 right는 모두 시간을 의미한다. 따라서 최소값인 left는 당연히 1이 되어야 할 것이다. 반면 최대값인 right는 먼저 주어진 cores에서 가장 오래 걸리는 작업 시간을 가진 값을 찾아주자. 그리고 그 값에 rest 값을 곱해주고 있는데 rest는 처리해야 할 나머지 작업의 개수를 의미한다. 이 값이 어떤 값인지는 바로 다음 챕터에서 확인하자. 다음으로는 이 값을 다시 코어의 개수로 나누어줘야 한다. 왜냐하면 문제에서 주어진 코어 모두가 최대시간만큼의 작업 시간을 가지고 있다고 가정할 때, 가장 오래 걸리는 시간을 측정할 수 있기 때문이다. 즉 rest개의 남은 작업을 X(최대값)의 처리 시간을 가진 코어 len개로 처리할 수 있는 시간을 구하는 것과 동일하다.

5) 이분탐색

자 그럼 left/right 값도 구했겠다, 바로 이분탐색을 실시해보자~ 라고 하기에 아직 한 가지 준비작업이 더 필요하다. 다시 위에서 그렸던 표로 돌아가보자. 우리는 여기서 초기 시간인 0H에 대해 이야기를 했었다. 이 시점에서는 모든 코어들이 비워져있기 때문에 바로 작업을 할당할 수 있다고 했다. 따라서 우리는 이 시점을 고려하여 이분탐색을 적용해주어야 할 필요가 있다.

이를 적용하는 것은 간단하다. 왜냐하면 초기에 할당 가능한 작업의 개수는 바로 코어의 개수와 동일하기 때문이다. 즉 이분탐색에서 구해주는 시간값인 mid값을 기준으로 처리하는 작업의 개수를 구하고, 이 값과 n - cores.length 값을 비교하며 이보다 크거나 작은 값을 만족하는 시간을 찾아주도록 하자. 그리고 n - cores.length가 위에서 언급한 rest가 될 것이다. 즉 rest는 초기에 할당된 작업을 제외한 나머지 처리해야할 작업의 수를 의미한다.

이때 매 이분탐색마다 mid값은 최소-최대 값 사이에 어떤 시간대가 설정될 것이다. 이 mid값에 몇개의 작업을 처리할 수 있는지 계산이 필요하다. 앞서 이야기한 바와 같이 해당 시간대에 처리가능한 작업의 개수와 위에서 구한 나머지 작업의 개수를 비교해야하기 때문이다. 이는 각 mid / cores[i] 의 몫의 누적합과도 같다. 왜냐하면 어떤 시간대 H가 주어졌을 때, 이에 해당하는 약수의 처리 시간을 가지고 있는 코어에 새로운 작업이 할당되었기 때문인데, 이 공식을 확장하면 다음이 성립하기 때문이다. 예시를 통해 알아보자.

• mid = 5이고, cores = [1, 2, 3] 일때 5시간까지 처리가능한 작업량의 수를 capacity라고 할 때

  • 5 / 1(첫 번째 코어) = 5
  • 5 / 2(두 번째 코어) = 2
  • 5 / 3(세 번째 코어) = 1
  • 따라서 capacity = 8

즉 mid = 5일때는 처리가능 한 작업의 수가 8임을 알 수 있다. 이때 총 작업량이 8이 아님에 주의하자. 왜냐하면 0H 시간대에 할당된 3개의 작업은 여기에 포함되지 않기 때문이다. 즉 초기값까지 모두 더해주면 결과값은 11이 됨을 알 수 있고, 이는 위에 표를 확인해보면 실제로 처리된 작업량이 11인 것을 확인할 수 있다.

이를 바탕으로 다음과 같이 이분탐색을 구현해보자. 이때 한 가지 주의해야 할 점은 n >= capacity를 만족하는 값을 찾아야 한다는 점이다. n과 동일한 것은 두 말 할 여지없이 우리가 찾는 값이고, 만약 이 값을 찾지 못하더라도 n보다 큰 최소 시간대에서 바로 그 이전 시간대의 작업량에서 n과 일치하는 코어의 위치를 찾을 수 있기 때문이다. 이와 관련해서는 다음 챕터에서 더 자세히 살펴보도록 하자.

const len = cores.length;

let rest = n - len;
let left = 1;
let right = Math.max(...cores) * rest / len;

// 최소값이 최대값을 초과하는 지점이 이분탐색 종료지점
while(left < right) {
  // mid는 항상 (최소+최대값)의 중간 지점 (소수점 버림)
  let mid = (left + right) / 2 >> 0;
  // mid값이 주어졌을 때 처리할 수 있는 총 작업의 수
  let capacity = 0;
  
  // capacity는 위에서 말한바와 같이 
  // (mid / core) 로 계산한 몫의 누적합
  for(const core of cores) {
    capacity += mid / core >> 0;
  }
  
  // 현재 작업의 총량이 실제값보다 크거나 같으면 right 범위 감소
  if(capacity >= rest) {
    right = mid;
    // 반대의 경우엔 left의 범위 증가
  } else {
    left = mid + 1;
  }
}

6) 마지막 작업 처리 코어의 위치 구하기

위의 이분탐색을 마친다면 right 값에는 rest의 작업량을 커버할 수 있는 마지노 선 시간대인 H가 담기게 될 것이다. 여기서 마지노 선이라는 것은 rest를 처리할 수 있는 시간대 중에서 가장 작은 시간을 의미한다.

이 시간을 가지고 우리는 마지막 작업을 처리하는 코어의 위치를 구할 수 있다. 다시 표를 그렸던 때로 돌아가보자. 거기서 우리는 특정 시간 H가 주어졌을 때, 작업량을 계산할 수 있음을 추출할 수 있었다. 이는 이분탐색 내에서도 현재 capacity를 계산할 때 적용했는데, 이분탐색이 끝나고도 똑같이 이를 이용해서 코어의 위치를 계산해보자.

현재 right는 운이 좋다면 해당 시간대에 마지막 작업을 처리하는 코어가 있을 수도 있지만, 이 값은 항상 rest와 일치한다는 것을 보장할 수 없다. 왜냐하면 우리는 capacity >= rest를 만족하는 조건에서 이분탐색을 수행했기 때문이다. 따라서 결과값에 담긴 right의 시간은 rest 만큼의 작업량보다 더 많은 작업을 처리한 시간대를 가리키고 있을 수 있다.

때문에 우리는 현재 right - 1의 시간대에서 처리된 작업량의 수를 먼저 구해주어야 한다. 이 역시 표를 그렸던 챕터에서 설명한 바 있다. 이전 시간대의 작업량 수를 계산하고, 이 값이 rest와 얼마나 차이나는지를 통해서 마지막 작업을 처리할 수 있는 코어의 위치를 계산할 수 있다.

따라서 이전 시간대인 right - 1에서 처리한 작업량을 구해주자. 이는 이분탐색에서 했던 것과 동일하게 구할 수 있다. 이 시간대에서 처리한 작업량을 현재 rest에서 제외한다면, 남은 값은 당연히 right 시간대에서 처리해야 할 작업량이 될 것 이다.

// right - 1 시간대에 처리한 작업량을
// 기존 rest에서 제외
// 따라서 rest에는 right 시간대에 처리할 작업만 남게 됨
for(const core of cores) {
  rest -= (right-1) / core >> 0;
}

이제 rest에는 현재 right 시간대에서 처리할 수 있는 작업만 담겨있다. 우리는 남아있는 작업을 몇 번째 코어가 처리할 수 있는지 위에서 이미 살펴보았다. 현재 시간대의 약수에 해당하는 코어라면 새로운 작업을 할당받을 수 있다. 따라서 현재 시간인 right를 코어의 처리 시간으로 나누어 떨어지는 순간이 바로 해당 코어가 새로운 작업을 할당받는 시점이 된다. 새로운 작업이 할당될 때 마다 rest는 1개씩 줄어들게 될 것이고, rest가 0이 되는 순간이 바로 마지막 작업을 처리하는 코어의 위치가 될 것이다.

// 코어의 수 만큼 반복문을 돌린다.
// 어차피 남아있는 rest의 수는 코어의 개수를 초과할 수 없다.
// 위 코드에서 현재 시간대에 처리할 수 있는 rest만 남겼기 때문이다.
// 이때 rest의 최대값은 코어의 개수와 동일하기 때문에
// 코어의 수 만큼 반복문을 돌리는 것
for(let i = 0; i < len; i++) {
  // 현재 시간과 코어의 처리시간이 나누어떨어지는 순간
  if(right % cores[i] === 0) {
    // 새 작업을 할당하기 때문에 남아있는 작업의 수를 1개 줄이고
    rest -= 1;
    // 만약 이때 남아있는 작업이 0이 되는 지점이라면
    if(!rest) {
      // 해당 코어의 인덱스를 반환
      // 문제에서 코어의 인덱스를 1부터 시작하도록 설정했으므로
      // 현재 인덱스에 1을 더한 값을 반환
      return i + 1;
    }
  }
}

7) 전체코드

이분탐색을 적용하는 문제 중에서도 나름 난이도가 높았던 문제 같다. 애초에 이분탐색 문제 자체가 개인적으로는 쉽게 '아 이 문제는 이분탐색 유형이구나!'를 파악하기 까다로운 경우가 많은데, 난이도 자체도 일반 문제보다 더 높았기 때문에 더 어려운 감이 있었다.

그리고 해당 문제는 사실 제한사항의 범위가 그렇게 크지 않기 때문에 우선순위 큐를 통해서도 사실 빠른 시간 내에 풀 수가 있다. 다만 해당 문제에서는 이분탐색을 적용한 기법만을 통과 케이스로 설정하려고 한 것인지 시간 복잡도를 굉장히 빡빡하게 설정한 듯 하다.

때문에 위 코드에서 rest 변수를 선언하는 부분에서 let 키워드를 사용해서 선언했는데, 이 경우에 효율성 테스트를 통과할 수 없다(특히 크롬에서 그 차이가 두드러진다). 오늘날 모던JS에서 var 키워드의 사용은 가급적 권장하지 않지만 성능 자체는 var 키워드가 let 키워드보다 빠르다. 때문에 let rest = n - len 부분을 var rest = n - len으로 바꾼다면 동일한 로직으로 효율성 테스트를 통과할 수 있다. 또는 인수로 넘어오는 n을 그대로 활용하여 별도의 변수 선언 없이 작성하는 방법도 있다.

위의 효율성 테스트 통과를 고려한 주석을 제외 전체코드는 다음과 같다.

function solution (n, cores) {
  const len = cores.length;
  
  var rest = n - len;
  let left = 1;
  let right = Math.max(...cores) * rest / len;
  
  while(left < right) {
    const mid = (left + right) / 2 >> 0;
    let capacity = 0;
    
    for(const core of cores) {
      capacity += mid / core >> 0;
    }
    
    if(capacity >= rest) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }
  
  for(const core of cores) {
    rest -= (right-1) / core >> 0;
  }
  
  for(let i = 0; i < len; i++) {
    if(right % cores[i] === 0) {
      rest -= 1;
      if(!rest) {
        return i + 1;
      }
    }
  }
}

출처

https://programmers.co.kr/learn/courses/30/lessons/12920