Level 3 210920
문제 설명
하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다.
예를들어
0ms 시점에 3ms가 소요되는 A작업 요청 - 1ms 시점에 9ms가 소요되는 B작업 요청 - 2ms 시점에 6ms가 소요되는 C작업 요청
와 같은 요청이 들어왔습니다. 이를 그림으로 표현하면 아래와 같습니다.
한 번에 하나의 요청만을 수행할 수 있기 때문에 각각의 작업을 요청받은 순서대로 처리하면 다음과 같이 처리 됩니다.
A: 3ms 시점에 작업 완료 (요청에서 종료까지 : 3ms) - B: 1ms부터 대기하다가, 3ms 시점에 작업을 시작해서 12ms 시점에 작업 완료(요청에서 종료까지 : 11ms) - C: 2ms부터 대기하다가, 12ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 16ms)
이 때 각 작업의 요청부터 종료까지 걸린 시간의 평균은 10ms(= (3 + 11 + 16) / 3)가 됩니다.
하지만 A → C → B 순서대로 처리하면
A: 3ms 시점에 작업 완료(요청에서 종료까지 : 3ms) - C: 2ms부터 대기하다가, 3ms 시점에 작업을 시작해서 9ms 시점에 작업 완료(요청에서 종료까지 : 7ms) - B: 1ms부터 대기하다가, 9ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 17ms)
이렇게 A → C → B의 순서로 처리하면 각 작업의 요청부터 종료까지 걸린 시간의 평균은 9ms(= (3 + 7 + 17) / 3)가 됩니다.
각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 배열 jobs가 매개변수로 주어질 때, 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마가 되는지 return 하도록 solution 함수를 작성해주세요. (단, 소수점 이하의 수는 버립니다)
제한 사항
- jobs의 길이는 1 이상 500 이하입니다.
- jobs의 각 행은 하나의 작업에 대한 [작업이 요청되는 시점, 작업의 소요시간] 입니다.
- 각 작업에 대해 작업이 요청되는 시간은 0 이상 1,000 이하입니다.
- 각 작업에 대해 작업의 소요시간은 1 이상 1,000 이하입니다.
- 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.
입출력 예
jobs
return
입출력 예 설명
문제에 주어진 예와 같습니다.
- 0ms 시점에 3ms 걸리는 작업 요청이 들어옵니다.
- 1ms 시점에 9ms 걸리는 작업 요청이 들어옵니다.
- 2ms 시점에 6ms 걸리는 작업 요청이 들어옵니다.
My solution
기존 방식대로 디스크 컨트롤러가 작동하면 평균 소요 시간이 길다. 하지만 작업 순서를 어떤 규칙에 따라 바꾸어주면 평균 소요 시간을 단축할 수 있다.
하나의 작업을 실행시키는 동안 3초의 시간이 걸렸다고 한다면 1~3초 안에 요청되어진 작업이 여러 개일 수 있다. 그렇다면 이 작업이 끝나고 3초가 되는 시점에 어떤 작업을 먼저 수행하는 것이 평균 소요 시간을 줄일 수 있을까?
평균 소요 시간은 작업의 요청부터 종료까지 걸린 시간의 평균으로, 대기하다가 작업시작 → 작업 완료의 과정이다. 작업 시작 → 작업 완료에 걸리는 시간은 정해져있으니 대기하는 시간을 최대한으로 줄이는 것이 평균 소요시간을 줄일 수 있는 방법이다.
따라서 요청되어 대기하고 있는 작업들을 가장 소요시간이 적은 것 순서대로 우선순위 큐(힙 자료구조)에 넣어 뽑아주면 된다.
힙 배열을 출력해보니 [26, 1], [37, 5], [43, 20], [24, 10],,,으로 들어가있다. 순서가 잘못 들어가있는 것을 보고 코드를 다시 확인했다.
heappush에서는 작업 소요 시간을 기준으로 계산해주었는데 아래처럼 heappop을 하는 함수 또한 작업 소요 시간을 기준으로 검사하도록 변경했다.(eg,. heap[left][1] < heap[next][1])
function heappop(heap) {
const res = heap.shift();
if (heap.length === 0) return res;
heap.unshift(heap.pop());
let idx = 0;
while (idx * 2 + 1 < heap.length) {
let next = idx;
const left = idx * 2 + 1;
const right = idx * 2 + 2;
if (heap[left][1] < heap[next][1]) next = left;
if (right < heap.length && heap[right][1] < heap[next][1]) next = right;
if (idx === next) break;
const temp = heap[idx];
heap[idx] = heap[next];
heap[next] = temp;
idx = next;
}
return res;
}이 문제가 레벨 3인 이유는 우선순위 큐(힙)를 사용해서 로직을 짜는 것이 어려운 것이 아닌 것 같다. 실질적으로 시간이 들었던 것은 아래의 로직이였다.
while (i < jobs.length) {
// 이전 작업의 시작 시점 < job의 작업 요청 시점 <= 현재 시점이어야 처리 가능
for (let x of jobs) if (start < x[0] && x[0] <= now) heappush(heap, x);
if (heap.length) {
let startJob = heappop(heap);
// startJob 시작 시점으로 업데이트, 현재 시점은 startJob 완료 후로 업데이트
start = now;
now += startJob[1]; // 현재 시점(startJob 완료 후)
// startJob 소요 시간 = 현재 시점(..) - startJob 요청 시점
answer += now - startJob[0];
i++;
} else now++; // 작업이 남아있으면 요청 시점이 올 때까지 1ms씩 증가
}전날에 풀었던 다리를 지나는 트럭 문제와 비슷하게 시간이 계속해서 흘러가는 동안 필요한 값들을 업데이트해주어야 했다.
여기에서는 jobs 배열 내의 job의 요청 시점이 현재 처리할 수 있는 시점인지 판단하기 위해서 "이전 작업의 시작 시점"부터 "현재 시점"을 구별할 변수가 필요했다. 왜냐하면 job의 요청 시점은 이전 작업의 시작 시점보다 빠를 수 없고 매번 그 범위를 바꾸어 주어야 그 시점에서 처리 가능한 모든 작업을 가져와서 그중 최소 소요 시간을 가진 작업으로 수행해줄 수 있기 때문이다.
이를 위해서는 아래의 로직이 필요하다.
- start를 현재 시점(now)으로 변경
- 현재 시점(now)을 startJob이 완료된 시점으로 변경,
- startJob이 완료된 현재 시점과 요청 시점의 차를 구해 총 소요 시간 계산
- 작업 수행에 의해 now가 계산되지 않을 때는 now++
이렇게 현재 처리 가능한 작업들을 우선순위 큐 구조에 맞춰 유지하고 heap의 원소가 존재하는 한(heap.length ≠= 0) heappop으로 소요시간이 가장 적은 작업을 꺼내서 answer에 총 소요 시간을 누적했다.
jobs의 원소의 개수만큼 작업이 완료되지 않았을 때 heap이 비어있다면 now(현재 시점)의 변수를 1ms씩 늘리면서 범위 바꾸며 job을 찾게 했다.
for (let x of jobs) if (start < x[0] && x[0] <= now) heappush(heap, x);아래의 예를 보면 요청 시점이 15로 같은 세 개의 작업이 있고 소요시간이 가장 적은 [15,2]가 heappop()되어 작업 완료되면서 now가 17로 바뀌게 되니 jobs에 있는 요청 시점이 17인 작업을 가져온다. 그리고 그 작업의 소요 시간이 가장 작다면 그것이 힙의 루트 노드에 존재할 것이고 heappop()을 사용해 꺼내서 먼저 처리한다.
소스 코드
function solution(jobs) {
let answer = 0,
start = -1,
now = 0,
i = 0;
let heap = [];
while (i < jobs.length) {
// 이전 작업의 시작 시점 < job의 작업 요청 시점 <= 현재 시점이어야 처리 가능
for (let x of jobs) if (start < x[0] && x[0] <= now) heappush(heap, x);
if (heap.length) {
let startJob = heappop(heap);
// startJob 시작 시점으로 업데이트, 현재 시점은 startJob 완료 후로 업데이트
start = now;
now += startJob[1]; // 현재 시점(startJob 완료 후)
// startJob 소요 시간 = 현재 시점(..) - startJob 요청 시점
answer += now - startJob[0];
i++;
} else now++; // 작업이 남아있으면 요청 시점이 올 때까지 1ms씩 증가
}
return Math.trunc(answer / jobs.length);
}
function heappush(heap, elem) {
heap.push(elem);
let idx = heap.length - 1;
while (idx > 0) {
const parent = Math.trunc((idx - 1) / 2);
// 소요 시간이 적은 것이 무엇인지 비교할 수 있도록 인덱스(eg,. [idx][1])로 지정
if (heap[idx][1] < heap[parent][1]) {
const temp = heap[parent];
heap[parent] = heap[idx];
heap[idx] = temp;
idx = parent;
} else {
break;
}
}
}
function heappop(heap) {
const res = heap.shift();
if (heap.length === 0) return res;
heap.unshift(heap.pop());
let idx = 0;
while (idx * 2 + 1 < heap.length) {
let next = idx;
const left = idx * 2 + 1;
const right = idx * 2 + 2;
if (heap[left][1] < heap[next][1]) next = left;
if (right < heap.length && heap[right][1] < heap[next][1]) next = right;
if (idx === next) break;
const temp = heap[idx];
heap[idx] = heap[next];
heap[next] = temp;
idx = next;
}
return res;
}
test("solution", () => {
// expect(
// solution([
// [0, 3],
// [1, 9],
// [2, 6],
// ])
// ).toBe(9);
expect(
solution([
[24, 10],
[28, 39],
[43, 20],
[37, 5],
[47, 22],
[20, 47],
[15, 34],
[15, 2],
[35, 43],
[26, 1],
])
).toBe(72);
});