[JS] 선입선출 스케줄링

이분탐색으로 해결할 수 있는 문제였다.

 

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

프로그래머스

 

 

문제는 단순한데 비해서 시간은 굉장히 오래걸린 문제였다.

 

효율성 부분이 굉장히 악독했다...

 

처음에는 우선순위 큐를 활용하여 선입선출 과정을 직접 구현하여 해결하려 했다.

 

class minQue {
  constructor() {
    this.ary = [0];
  }
  swap(a, b) {
    [this.ary[a], this.ary[b]] = [this.ary[b], this.ary[a]];
  }

  push(value) {
    let idx = this.ary.length;
    this.ary.push(value);
    while (0 < idx) {
      const parent = ~~(idx / 2);
      if (this.ary[parent][1] > this.ary[idx][1]) {
        this.swap(idx, parent);
        idx = parent;
        continue;
      }
      break;
    }
  }
  size() {
    return this.ary.length - 1;
  }

  pop() {
    if (this.ary.length === 1) return undefined;
    if (this.ary.length === 2) return this.ary.pop();

    const ret = this.ary[1];
    this.ary[1] = this.ary.pop();
    let idx = 1;
    while (idx < this.ary.length) {
      const [left, right] = [idx * 2, idx * 2 + 1];
      if (left >= this.ary.length) break;
      let minIdx = left;
      if (right < this.ary.length && this.ary[left][1] > this.ary[right][1])
        minIdx = right;
      if (this.ary[idx][1] > this.ary[minIdx][1]) {
        this.swap(idx, minIdx);
        idx = minIdx;
        continue;
      }
      break;
    }

    return ret;
  }
  //processQue에서만 사용
  runTime() {
    const [core, time] = this.pop();
    const ret = [[core, time]];
    while (this.ary[1][1] === time) ret.push(this.pop());
    return ret;
  }
}

function solution(n, cores) {
  const cpu = cores.map((v, i) => [v, 0]);

  const waitingQue = new minQue(); // [작업시간,큐번호]
  const processQue = new minQue(); // [큐번호,끝나는 작업시간]
  for (let i = cores.length - 1; i >= 0; i--) {
    waitingQue.push([cores[i], i]);
  }

  let curTime = 0;
  for (let i = 0; i < n; i++) {
    if (!waitingQue.size()) {
      const tmpWaitingQueCore = processQue.runTime();
      curTime = tmpWaitingQueCore[0][1];

      for (const [core, t] of tmpWaitingQueCore) {
        waitingQue.push([cores[core], core]);
      }
    }

    const [t, core] = waitingQue.pop();
    processQue.push([core, t + curTime]);
    if (i === n - 1) return core + 1;
  }
}

 

 

정확도 테스트는 모두 통과했지만 효율성테스트를 통과하지 못했다.

곰곰히 생각을 해보다가 이분탐색이란 키워드를 생각해냈다.

 

문제에서 요구하는 것은 모든 이분탐색이 끝났을때의 시간이 아니다. 바로 n번째 작업이 몇번째 코어에서 발생하는지이다.

 

이분탐색을 활용한다면 해당 작업이 진행될때의 시간을 알 수 있다! 따라서 시간을 활용하여 마지막 작업이 몇번 코어에서 작동하는지를 알아내면 된다. 단, 이 부분에서 생각할 점이 있다.

 

문제에서 제공한 예시를 보자

 

 

시간   작업량

0       3

1        4

2       6

3       8

 

 

만약 5 ,[1,2,3] 이 문제 케이스로 들어왔다고 생각해보자.

작업량의 기준이 4에서 6으로 한번에 뛰기 때문에 시간의 정답은 2로 나오겠지만 n이 5,6이 두 경우를 모두 생각해줘야 한다.

 

이는 생각보다 단순하게 해결할 수 있었다.

 

core가 걸린시간에 딱 나누어 떨어지는 경우가 마지막 시간에 진행될 수 있는 작업들이다. 

 

4 -> 6으로 건너뛰는 경우 0번째와 1번째 코어가 사용된다는 것을 위 방법을 통해 알 수 있다.

 

 

5   --> [0,1]

6   --> [0,1]

 

5번째 작업은 0이, 6번째 작업은 1이 한다는 걸 활용해서 정답을 구해주면 된다.

 

 

 

 

function solution(n, cores) {
    
    const getWorkCnt = (time) => {
        return cores.reduce((a,c) => a + ~~(time/c),0) + cores.length
    }
    
    let right = 5000*50000;
    let left = 1
    
    while(left <= right) {
        const mid = ~~((right+left)/2)
        const work = getWorkCnt(mid)
        if(work >= n) right = mid -1
        else left = mid+1
    }
    
    const work = getWorkCnt(left)
    let ret = []
    for (let i = 0 ; i < cores.length ; i++){
        if(!(left%cores[i])) ret.push(i)
    }
    
    return ret[ret.length-work+n-1] + 1
}