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

디스크 컨트롤러 문제 바로가기

요약

주어진 작업들을 가장 빨리 처리한다고 했을 때 작업 당 평균적으로 얼마의 시간이 필요로 한지를 구하는 문제이다.

문제의 조건에서, 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리한다고 되어 있다. 따라서 특정 시간에 수행할 수 있는 작업이 하나일 경우 묻지도 따지지도 않고 해당 작업을 수행하면 된다.

내 고민

이 문제에서 고민이 필요했던 부분은 특정 시간에 여러 작업이 쌓여있을 경우 어떤 작업을 먼저 수행해야할지였다. 처음에는 “작업의 요청부터 종료까지 걸린 시간”이 제일 작은 작업을 선택하는 방식으로 알고리즘을 만들었다. 하지만 35점이라는 점수를 받았다.

그래서 “질문하기”를 참고하니 단순히 작업의 소요시간이 가장 짧은 것을 선택하면 정답이다라는 글을 봤다. 그래서 따라하니까 정답이 맞긴 했다.

그렇다면 왜 작업의 소요시간이 가장 짧은 것을 선택해야 할까?

생각보다 그 이유는 간단했다. 작업의 소요시간이 가장 짧은 것을 선택해야 그만큼 주어진 시간에 많은 작업을 처리할 수 있기 때문이다.

예를 들어, 작업 소요시간이 각각 3, 10, 20초인 작업들이 있다고 가정하자. 만약 20초인 작업을 먼저 처리한다면 3, 10초인 작업들의 작업시간은 최소 20초씩 늘어난다. 하지만 3초 작업을 먼저 처리한다면 10, 20초 작업의 작업 시간은 최소 3초씩만 늘어나게 된다.

그렇다면 여러 작업들 중에 작업의 소요시간이 가장 짧은 작업을 뽑아내려면 어떻게 해야될까? 단순히 Jobs를 모두 순회하는 방식으로는 O(n)의 시간복잡도를 갖는다.

이때 최소힙을 사용하면 O(logN)의 시간복잡도 만으로 처리할 수 있다.

하지만 Swift에서는 힙을 지원하지 않기 때문에 직접 구현해야 한다. 문제에 맞는 힙을 직접 구현하면 좋겠지만 아직 그정도 수준이 아니기 때문에 우선은 범용적으로 사용할 수 있는 힙을 만들고 그 힙을 이용하여 문제를 풀어보도록 하겠다.

최소힙

코드가 다소 길어보이기는 하지만 원리를 이해하면 쉽게 짤 수 있다. (이 곳을 참고하면 쉽게 이해할 수 있다!)

struct Heap<T: Comparable> {
    var heap = [T]()
    
    init() {}
    init(data: T) {
        heap.append(data)
        heap.append(data)
    }
}

extension Heap {
    mutating func insert(_ data: T) {
        guard !heap.isEmpty else {
            heap.append(data)
            heap.append(data)
            return
        }
        
        heap.append(data)
        
        func isMovingUp(_ index: Int) -> Bool {
            guard index > 1 && self.heap.count > index else { return false }
            
            let parentIndex = index / 2
            if self.heap[index] < self.heap[parentIndex] {
                return true
            } else {
                return false
            }
        }
        
        var index = self.heap.count - 1
        while isMovingUp(index) {
            let parentIndex = index / 2
            self.heap.swapAt(index, parentIndex)
            index = parentIndex
        }
    }
    
    mutating func pop() -> T? {
        guard self.heap.count > 1 else { return nil }
        
        let result = self.heap[1]
        self.heap.swapAt(1, heap.count - 1)
        self.heap.removeLast()
        
        func swapIfNeeded(_ index: Int) {
            let leftChildIndex = index * 2
            let rightChildIndex = leftChildIndex + 1
            
            let hasNoChild = self.heap.count <= leftChildIndex
            if hasNoChild {
                return
            }
            
            let hasOnlyLeftChild = self.heap.count > leftChildIndex && self.heap.count <= rightChildIndex
            if hasOnlyLeftChild {
                if self.heap[index] > self.heap[leftChildIndex] {
                    self.heap.swapAt(index, leftChildIndex)
                    swapIfNeeded(leftChildIndex)
                    return
                } else {
                    return
                }
            }
            
            // 자식이 모두 있는 경우
            if self.heap[leftChildIndex] < self.heap[rightChildIndex] && self.heap[leftChildIndex] < self.heap[index] {
                self.heap.swapAt(index, leftChildIndex)
                swapIfNeeded(leftChildIndex)
                return
            } else if self.heap[leftChildIndex] > self.heap[rightChildIndex] && self.heap[rightChildIndex] < self.heap[index] {
                self.heap.swapAt(index, rightChildIndex)
                swapIfNeeded(rightChildIndex)
                return
            } else {
                return
            }
        }
        
        swapIfNeeded(1)
        
        return result
    }
}

하지만 힙을 사용하면서 문제에 봉착했다. 힙이 단순히 ‘작업의 소요시간’만 들고 있으면 ‘작업이 요청되는 시점’을 알 수 없게 된다. 따라서 Comparable을 채택하는 Job이라는 구조체를 만들어 힙이 Job 구조체를 들고 있게 하였다. 애초에 힙은 Comparable을 채택하는 자료형만 받고 있기 때문에 힙 구조체를 변경할 필요는 없다.

struct Job: Comparable {
    static func < (lhs: Job, rhs: Job) -> Bool {
        if lhs.dueTime < rhs.dueTime {
            return true
        } else {
            return false
        }
    }
    
    static func == (lhs: Job, rhs: Job) -> Bool {
        if lhs.dueTime == rhs.dueTime && lhs.startTime == rhs.startTime {
            return true
        } else {
            return false
        }
    }
    
    let dueTime: Int
    let startTime: Int
    init(_ dueTime: Int, _ startTime: Int) {
        self.dueTime = dueTime
        self.startTime = startTime
    }
}

최종

힙 자체는 O(logN)의 시간 복잡도를 갖지만 처리된 job을 지워나가는 과정에서 O(N)의 시간복잡도가 드는 것을 확인했다. 그래서 Job 구조체에 index라는 변수를 하나 더 추가하여 해당 Job이 Jobs에서 몇 번째에 있는지 탐색하는 과정이 필요없도록 하였다. 이렇게 만들고 돌려보니 테스트 시간이 확연히 짧아진 것을 확인할 수 있었다.

struct Job: Comparable {
    static func < (lhs: Job, rhs: Job) -> Bool {
        if lhs.dueTime < rhs.dueTime {
            return true
        } else {
            return false
        }
    }
    
    static func == (lhs: Job, rhs: Job) -> Bool {
        if lhs.dueTime == rhs.dueTime && lhs.startTime == rhs.startTime {
            return true
        } else {
            return false
        }
    }
    
    let dueTime: Int
    let startTime: Int
    let index: Int
    init(_ dueTime: Int, _ startTime: Int, _ index: Int) {
        self.dueTime = dueTime
        self.startTime = startTime
        self.index = index
    }
}

func solution(_ jobs:[[Int]]) -> Int {
    var remainJobs = jobs
    var jobCount = jobs.count
    var result = 0
    var currentTime = 0
    
    while !remainJobs.isEmpty {
        var heap = Heap<Job>()
        for (index, job) in remainJobs.enumerated() {
            if job[0] <= currentTime {
                // 작업의 소요 시간, 작업이 요청되는 시점
                heap.insert(Job(job[1], job[0], index))
            }
        }
        
        if let resolvedJob = heap.pop() {
            result += currentTime - resolvedJob.startTime + resolvedJob.dueTime
            currentTime += resolvedJob.dueTime
            remainJobs.remove(at: resolvedJob.index)
        } else {
            currentTime += 1
        }
    }
    
    return result / jobCount
}