디스크 컨트롤러
📚 문제 설명
진행해야할 작업이 [작업 요청 시간, 작업 시간] 으로 주어진다고 한다.
아래 조건에 맞게 작업을 진행할 때, 작업 요청 시간부터 실재 작업이 끝날 때까지 걸린 시간의 평균이 최소인 경우를 구하라.
조건
- jobs의 길이는 1 이상 500 이하입니다.
- jobs의 각 행은 하나의 작업에 대한 [작업이 요청되는 시점, 작업의 소요시간] 입니다.
- 각 작업에 대해 작업이 요청되는 시간은 0 이상 1,000 이하입니다.
- 각 작업에 대해 작업의 소요시간은 1 이상 1,000 이하입니다.
- 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.
예를 들어 설명하면 아래와 같다.
다음과 같이 A, B, C 3가지 일이 주어졌을 때,
A : [0, 3]
B : [1, 9]
C : [2, 6]
평균이 최소가 되는 경우는 아래와 같다.
3 + 7 + 17 = 27
평균 : 9
👨🏻💻 풀이 과정
처음에는 이 문제를 읽고 모든 작업을 Priority Queue인 MinHeap에 넣고 작업 시간이 짧은 순으로 꺼내면 될 것 같았다.
그러나 해당 풀이는 다음 조건 때문에 불가능하다.
하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.
현재 시간에 따라 MinHeap에 요청이 온 일들을 넣어주고.
MinHeap 에서 작업 시간이 짧은 순으로 꺼내서 작업을 진행하는 방식으로 구현하고자 했다.
그렇게 구현한 로직은 다음과 같다.
jobs배열이 작업 요청순으로 내림차순으로 올 수 있도록 정렬.jobs배열에 원소가 있다면,MinHeap에 가장 빨리 오는 작업을INSERT()(만약 하나의 작업이 끝나고 다음 작업까지 대기 시간이 있을 경우를 위해)MinHeap에 원소가 있다면, 최소 값을 꺼내서 작업 시간을 더해주고,jobs배열에서 현재 작업 시간 이전에 들어온 작업들을 모두MinHeap에INSERT()answer배열에 각각의 작업의 요청부터 소요된 시간 계산
전체 로직 코드
// 로컬 실행을 위해 변수 생성
let jobs = [[1, 4], [7, 9], [1000, 3]];
// Min
class MINHAP {
//생략
}
// 메인 로직 함수
const solution = () => {
let time = 0;
let answer = [];
const MinHeap = new MINHEAP();
// 작업들이 시작순으로 정렬되도록. (혹시나 시작 시간이 같을 경우를 위해 조건을 넣긴 했으나 불필요함)
jobs.sort((a, b) => {
if (a[0] === b[0]) {
return b[1] - a[1];
} else {
return b[0] - a[0];
}
});
// 만약 작업이 끝나고 다음 작업까지 아무일 없을 경우를 위해
while (jobs.length) {
MinHeap.INSERT(jobs.pop());
// 만약 힙에 값이 있다면
while (MinHeap.GetLength() > 0) {
const Min = MinHeap.POP();
// 만약 작업이 끝나고 대기 시간이 있었을 경우를 위해
if (Min[0] > time) {
time = Min[0];
}
// 현재 시간에서 작업 진행 시간을 더해줌
time += Min[1];
// jobs 배열에 현재 시간 이전에 요청된 작업이 있는지 확인
while (jobs.length) {
if (jobs[jobs.length - 1][0] <= time) {
MinHeap.INSERT(jobs.pop());
}else break;
}
answer.push(time - Min[0]);
}
}
// 소숫점 버림, 평균값 계산
return Math.floor(answer.reduce((a, b) => a + b) / answer.length);
}
console.log(solution());
💡Min Heap 구현
해당 문제에서는 일단 아래와 같은 조건이 없다.
- 동시에 작업이 들어올 수는 없다.
- 작업 시간이 같을 수는 없다.
따라서 우리는 이 점을 유의하며 구현을 진행해야 한다.
만약 작업 시간이 같을 경우 먼저 들어온 일을 우선한다.
class MINHEAP {
constructor() {
this.heap = [null];
}
INSERT(item) {
let Current = this.heap.length;
while (Current > 1) {
const Parent = Math.floor(Current / 2);
if (this.heap[Parent][1] > item[1]) {
this.heap[Current] = this.heap[Parent];
Current = Parent;
} else if (this.heap[Parent][1] === item[1]) {
if (this.heap[Parent][0] > item[0]) {
this.heap[Current] = this.heap[Parent];
Current = Parent;
} else break;
} else break;
}
this.heap[Current] = item;
}
POP() {
const PopElement = this.heap[1];
if (this.heap.length > 2) {
this.heap[1] = this.heap.pop();
let Current = 1;
let LeftChild = Current * 2;
let RightChild = Current * 2 + 1;
while (this.heap[LeftChild]) {
let Compare = LeftChild;
if (this.heap[RightChild]) {
if (this.heap[LeftChild][1] > this.heap[RightChild][1]) {
Compare = RightChild;
} else if (this.heap[LeftChild][1] === this.heap[RightChild][1]) {
if (this.heap[LeftChild][0] > this.heap[RightChild][0]) {
Compare = RightChild;
}
}
}
if (this.heap[Current][1] > this.heap[Compare][1]) {
[this.heap[Current], this.heap[Compare]] = [this.heap[Compare], this.heap[Current]];
Current = Compare;
} else if (this.heap[Current][1] === this.heap[Compare][1]) {
if (this.heap[Current][0] > this.heap[Compare][0]) {
[this.heap[Current], this.heap[Compare]] = [this.heap[Compare], this.heap[Current]];
Current = Compare;
} else break;
} else break;
LeftChild = Current * 2;
RightChild = Current * 2 + 1;
}
} else if (this.heap.length === 2) {
this.heap.pop();
} else {
return null;
}
return PopElement;
}
GetLength() {
return this.heap.length - 1;
}
}전체 코드
function solution(jobs) {
class MINHEAP {
constructor() {
this.heap = [null];
}
INSERT(item) {
let Current = this.heap.length;
while (Current > 1) {
const Parent = Math.floor(Current / 2);
if (this.heap[Parent][1] > item[1]) {
this.heap[Current] = this.heap[Parent];
Current = Parent;
} else if (this.heap[Parent][1] === item[1]) {
if (this.heap[Parent][0] > item[0]) {
this.heap[Current] = this.heap[Parent];
Current = Parent;
} else break;
} else break;
}
this.heap[Current] = item;
}
POP() {
const PopElement = this.heap[1];
if (this.heap.length > 2) {
this.heap[1] = this.heap.pop();
let Current = 1;
let LeftChild = Current * 2;
let RightChild = Current * 2 + 1;
while (this.heap[LeftChild]) {
let Compare = LeftChild;
if (this.heap[RightChild]) {
if (this.heap[LeftChild][1] > this.heap[RightChild][1]) {
Compare = RightChild;
} else if (this.heap[LeftChild][1] === this.heap[RightChild][1]) {
if (this.heap[LeftChild][0] > this.heap[RightChild][0]) {
Compare = RightChild;
}
}
}
if (this.heap[Current][1] > this.heap[Compare][1]) {
[this.heap[Current], this.heap[Compare]] = [this.heap[Compare], this.heap[Current]];
Current = Compare;
} else if (this.heap[Current][1] === this.heap[Compare][1]) {
if (this.heap[Current][0] > this.heap[Compare][0]) {
[this.heap[Current], this.heap[Compare]] = [this.heap[Compare], this.heap[Current]];
Current = Compare;
} else break;
} else break;
LeftChild = Current * 2;
RightChild = Current * 2 + 1;
}
} else if (this.heap.length === 2) {
this.heap.pop();
} else {
return null;
}
return PopElement;
}
GetLength() {
return this.heap.length - 1;
}
}
const main = () => {
let time = 0;
let answer = [];
const MinHeap = new MINHEAP();
jobs.sort((a, b) => {
if (a[0] === b[0]) {
return b[1] - a[1];
} else {
return b[0] - a[0];
}
});
while (jobs.length) {
MinHeap.INSERT(jobs.pop());
while (MinHeap.GetLength() > 0) {
const Min = MinHeap.POP();
if (Min[0] > time) {
time = Min[0];
}
time += Min[1];
while (jobs.length) {
if (jobs[jobs.length - 1][0] <= time) {
MinHeap.INSERT(jobs.pop());
}else break;
}
answer.push(time - Min[0]);
}
}
return Math.floor(answer.reduce((a, b) => a + b) / answer.length);
}
return main();
}🧐 후기
최소힙을 사용하는 문제인데, 최소힙을 조건에 맞게 계속 갱신을 해야한다는 점에서 고민이 되었던 문제였다.
JavaScript를 사용하는 모두를 위해...