문제 출처
나의 풀이(실패)
/**
* 대기열과 현재 작업열을 나누고,
* 대기열에 없으면 => 가장 먼저 시작하는 작업을 가져오고
*
* 작업 중에 뭔가를 찾으면 대기열로 넣어두고
* 작업이 끝나면, 대기열에 있는 애들을 가지고 우선순위를 따진다.
* ...
*
* => 작업 중 다른 요청이 들어오면
* 1. 1건만 들어온 경우 작업이 끝나고 바로 처리 (요청순)
* 2. 2건 이상인 경우 처리 시간이 짧은 항목부터 처리
*/
function solution(jobs) { // 틀린 풀이
let answer = [0, 0]
jobs.sort((a,b) => a[0] - b[0])
let ing = [jobs[0]]
let ch = new Array(jobs.length).fill(0)
ch[0]=1
while(ing.length){
const [start, work] = ing.shift()
// console.log((answer[0] + work) - start)
answer[0] += (answer[0] + work) - start
answer[1] += 1
for(let i=0; i<jobs.length; i++){
if(jobs[i][0] >= start && jobs[i][0] <= answer[0]){
if(ch[i] === 0) {
ing.push(jobs[i])
ch[i]=1
}
}
}
if(ing.length >= 2){
ing.sort((a,b) => (a[1]-a[0]) - (b[1]-b[0]))
}
}
return answer[0]/answer[1] >> 0
}
console.log(solution([[0, 3], [1, 9], [2, 6]]))나는 for 반복문을 통해 진행하려 했으나 각 i마다 처리해야 할 게 많고 i++이 되는 경우의 수가 너무 많았다. 이럴 때는 for문으로 i++를 처리하는 게 아니라 while문을 통해 수동으로 i++이 정말 필요할 때만 처리되도록 코드를 작성해야 한다.
다른 풀이
문제 해석은 다음과 같다.
대기열(우선순위 큐)과 현재 처리열을 구분한다.
대기열에 아무것도 없으면, 작업 요청 시점이 가장 빠른 것부터 처리하기 위해 정렬을 해준다. jobs.sort((a,b) => a[0] - b[0])
작업 소요 시간 동안 다른 작업 요청이 들어오면 대기열에 넣어놓는다. 이때 대기열에 들어간 작업들은 처리 시간이 짧은 작업부터 처리하기 위해 소요 시간을 기준으로 정렬을 한다.
이때 한번이라도 작업 중에 작업 요청이 있다면 i++를 해주면서 다른 작업도 요청이 있는지 확인한다.
하나의 작업을 끝내면
우선순위 큐에 남아 있는 작업을 확인하는데,
- 없으면 소요시간을 업데이트해주고
- 있으면 그에 맞게 shift로 처리해준다.
function solution(jobs) {
let answer = 0
jobs.sort((a,b) => a[0] - b[0])
const pq = [] // 우선순위 큐 (priority Queue)
let i = 0 // 각 작업이 처리되면 i++
let time = 0 // 소요 시간 보다 작을 때 작업이 추가되면 우선순위 큐에 삽입한다.
while(i < jobs.length || pq.length !== 0){
// 작업 중 요청이 들어온 경우 (== 우선순위 큐에 삽입)
if(i < jobs.length && jobs[i][0] <= time){
pq.push(jobs[i++])
pq.sort((a,b) => a[1] - b[1]) // 우선순위 큐 내에서 소요시간으로 정렬
continue // 한번 작업 중 요청이 들어왔다면 다른 요청도 있는지 확인하기 위해
}
// 대기열에 요청 작업이 없을 때
if(pq.length === 0){
time = jobs[i][0]
} else { // 대기열에 요청 작업들이 있을 때
const [start, work] = pq.shift()
answer += (time + work) - start
time += work
}
}
return parseInt(answer / jobs.length)
}이러한 로직은 SJF(Shortest Job First)과 동일하다.
- 작업 처리의 평균시간을 최소로 하려면, 실행시간이 가장 짧은 프로세스부터 먼저 처리하면 된다. => 그러므로 정렬을 한 뒤 그리디하게 풀 수 있다.
이 문제는 SJF 중에서도 비선점 SJF 알고리즘에 해당한다. 이전 프로세스가 처리될 때까지 기다려야 한다.
다른 풀이 (heap으로 구현)
작업 대기열인 heap만 구현하면 로직은 동일하다.
작업 소요 시간을 기준으로 최소 힙을 생성한다.
class Heap {
constructor(){
this.item = []
}
get length(){
return this.item.length
}
get heap(){
return this.item
}
getParent(idx){
return Math.floor((idx - 1) / 2)
}
getLeftChild(idx){
return idx * 2 + 1
}
getRightChild(idx){
return idx * 2 + 2
}
swap(a, b){
;[this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]]
}
bubbleUp(idx){
if(idx < 0) return
const left = this.getLeftChild(idx)
const right = this.getRightChild(idx)
const swapChildren =
this.item[right] && this.item[right][1] < this.item[left][1]
? right
: left
if(this.item[swapChildren][1] < this.item[idx][1]){
this.swap(swapChildren, idx)
this.bubbleUp(this.getParent(idx))
}
}
bubbleDown(idx){
if(idx > Math.floor(this.length / 2) - 1) return
const left = this.getLeftChild(idx)
const right = this.getRightChild(idx)
const swapChildren =
this.item[right] && this.item[right][1] < this.item[left][1]
? right
: left
if(this.item[swapChildren][1] < this.item[idx][1]){
this.swap(swapChildren, idx)
}
this.bubbleDown(swapChildren)
}
shift(){
this.swap(0, this.length - 1)
const pop = this.item.pop()
this.bubbleDown(0)
return pop
}
push(value){
this.item.push(value)
this.bubbleUp(this.getParent(this.length - 1))
}
}
function solution(jobs){
const heap = new Heap()
const length = jobs.length
let answer = 0
let time = 0
jobs = jobs
.sort((a,b) => a[0] - b[0])
.map((v, _, ori) => [v[0] - ori[0][0], v[1]])
while(jobs.length || heap.length){
while(jobs.length && jobs[0][0] <= time){
heap.push(jobs.shift())
}
if(!heap.length){
const newTime = jobs[0][0]
while(jobs.length && jobs[0][0] === newTime){
heap.push(jobs.shift())
}
time = newTime
}
const done = heap.shift()
time += done[1]
answer += time - done[0]
}
return Math.floor(answer / length)
}참고
https://medium.com/@wooleejaan