[프로그래머스] 디스크 컨트롤러

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

코딩테스트 연습 - 디스크 컨트롤러

그림과 같은 요청이 들어왔을 때 (시작 시간, 수행 시간)을 고려하여 적절히 배치하였을 때, 총 수행시간의 평균이 최소가 되도록 하는 경우를 찾으면 되는 문제이다! (한 번에 하나씩만 수행 가능)

 

FIFO

위 방법은 그저 들어온 순서대로 즉, FIFO의 형태로 수행된 결과이다. 

물론 최적의 값은 아니다. 

SJF

이렇게 수행시간이 짧은 순서대로 배치하여 진행하는 것이 최소의 평균값을 구할 수 있다고 한다. 

이걸 SJF ( Shortest Job First )라고 한다. 

 

그러니 주어진 배열을 먼저 정렬해줄 필요가 있다. 

 

1. 수행시간을 기준으로 오름차순 정렬해준다. 단, 수행 시간이 같을 경우 시작 시간이 짧은 걸 먼저 배치하는 방식으로 정렬한다. 
2-1. 정렬한 배열을 기준으로 시작 시간이 현재 시간보다 앞설 경우 수행을 시작한다. 
    2-1-1. 현재 시간에 수행 시간을 누적시킨다 ( 즉, 현재 시간을 하나의 작업이 끝난 시점으로 변경해주는 것 )
    2-1-2. 총 합에 현재 시간 - 시작 시간을 더하여 누적한다. 
    2-1-3. 수행한 작업은 배열에서 제외해준다. 
    2-1-4. 다시 맨 처음으로 돌아간다. 
2-2. 그러지 않을 경우 time += 1 해주어, 차례를 기다리고 있는 작업의 시작 시간에 가까워지도록 한다. 
3. 총 결과 / 총 개수 반환

 

바로 전체 코드로 가보자.

import Foundation

func solution(_ jobs:[[Int]]) -> Int {
    // 합, 현재 시간
    var sum = 0, time = 0
    // SJF (Shortest Job First)
    // 수행 시간이 같다면, 시작 시간이 빠른 순서대로 정렬 아닐 경우 수행 시간이 짧은 순서대로!
    var SortedJobs = jobs.sorted { $0[1] == $1[1] ? $0[0] < $1[0] : $0[1] < $1[1] }
    
    while !SortedJobs.isEmpty {
        for i in 0..<SortedJobs.count {
            let startT = SortedJobs[i][0]
            let processT = SortedJobs[i][1]
            
            // 시작 시간이 현재 시간보다 앞서는 경우            
            if startT <= time {
                print(time, startT,processT)
                // 수행 시간 누적
                time += processT
                // 요청부터 종료까지 소요 시간 누적
                sum += (time - startT)
                SortedJobs.remove(at: i)
                break
            }
            
            // 아무런 경우도 위에 해당하지 않아 idx가 끝까지 온 경우 1초 추가
            if i == SortedJobs.count - 1 {
                time += 1
            }
        }
    }
    
    // 평균
    return sum / jobs.count
}

하나하나씩 뜯어보면 핵심이 되는 부분이 있다.

2개의 케이스로 나눠서 살펴보자.  

for i in 0..<SortedJobs.count {
    let startT = SortedJobs[i][0]
    let processT = SortedJobs[i][1]

    // 시작 시간이 현재 시간보다 앞서는 경우            
    if startT <= time {
    	print(time, startT,processT)
        // 수행 시간 누적
        time += processT
        // 요청부터 종료까지 소요 시간 누적
        sum += (time - startT)
        SortedJobs.remove(at: i)
        break
    }

    // 아무런 경우도 위에 해당하지 않아 idx가 끝까지 온 경우 1초 추가
    if i == SortedJobs.count - 1 {
    	time += 1
    }
}

첫 번째 if문의 경우, 현재 시간과 비교하여 시작 시간이 더 이를 경우 작업에 착수하게 해준다. 

 

예를 들어 위의 케이스일 때, 1 > 2 > 3의 순서대로 수행되게 된다. 

하지만 한 번에 하나씩만 수행 가능하기 때문에 겹쳐 있는 부분들을 피해줘야 한다. 

// 시작 시간이 현재 시간보다 앞서는 경우            
if startT <= time {
    print(time, startT,processT)
    // 수행 시간 누적
    time += processT
    // 요청부터 종료까지 소요 시간 누적
    sum += (time - startT)
    SortedJobs.remove(at: i)
    break
}

그 부분을 바로 위 코드가 책임진다. 

 

우선 현재 시간을 기준으로 시작 시간과 비교하고, 수행 가능한 작업이 있다면 착수한 뒤 바로 for문을 나오게 된다. 

즉, 한 번에 하나만 수행하기 위해 time을 계산하고 그 뒤에서부터 다시 수행시간이 짧은 것(시작 시간 < 현재 시간)에 착수하는 것이다. 

 

그림으로 보면 이해가 빠를텐데, 마치 킵(keep)해두는 것과 같다.

킵 해둔 것 중에서 수행 시간이 빠른 것을 먼저 배치하고, 이를 계속 반복하게 되는 것이다. 

 

점선의 작업들은 대기

 

만약에 다음의 경우는 어떨까? 

 

1과 2 작업 사이에 텀이 있는 것을 볼 수 있다. 

 

이처럼 작업 수행 뒤, 바로 기다리고 있는 작업이 무조건 있지는 않을 것이라는 것이다. 

그렇기에 현재 시간과 비교하는 부분에서 기다리는 작업이 없다면, 아무런 작업을 수행하지 못하고 시간만 늘어나게 되는 것이다 (time += 1)

// 아무런 경우도 위에 해당하지 않아 idx가 끝까지 온 경우 1초 추가
if i == SortedJobs.count - 1 {
    time += 1
}

---

실제로 OS에서 불리우는 스케줄링에서 사용되는 SJF를 활용한 방식으로 풀이되었다. 

사전에, 수행 시간을 기준으로 정렬해두고 그 때 시점에 맞게 적절한 작업을 배치해주면 최적의 값을 구할 수 있었던 문제였다.