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

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

프로그래머스

 

2023.07.21 기준 Level 3

 

알고리즘 공부를 위해 풀고 기록하는 글입니다!
참고만 해주시고 더 좋은 풀이법이 있다면 알려주세요!

 

아이디어

작업 시간의 평균을 가장 줄이는 방법은 들어온 작업 중에서 소요 시간이 가장 작은 작업부터 진행하는 것입니다!

운영체제의 Process Scheduling에서의 SJF 스케줄링과 같은 내용입니다.

 

1. 현재 시각을 나타내는 변수를 생성
2. 현재 시각까지 요청 들어온 Job들 중에서 소요 시간이 가장 작은 작업을 선택
3. 해당 작업을 진행
4. 현재 시각에 3번에서 진행한 작업에서 소요된 만큼을 더해준다.
5. 작업들을 모두 끝낼 때까지 1~4번 작업을 반복

이러한 순서로 코드를 구현하고자 했습니다!

 

우선 2번을 구현하는 것이 핵심인데 여러개의 데이터 중에서 특정 값이 가장 작거나 큰 경우를 뽑을 때는 Heap이 적합한 자료구조입니다.

O(logN)의 시간 복잡도로 insert와 remove가 가능하기 때문입니다. (이 문제의 분류 자체도 Heap이기 때문에 힌트가 되었습니다.)

우리는 작업들 중에서 소요 시간이 가장 작은 작업을 뽑아야 하기 때문에 최소 Heap을 사용해야 합니다!

 

Heap을 한번 감싼 Priority Queue를 사용해도 무방합니다.

 

 

풀이

1. Heap 구현

import Foundation

public struct Heap<T: Comparable> {
    
    // MARK: - Properties
    
    private var elements = [T]()
    private let sortFunction: (T, T) -> Bool
    
    /// O(1)
    public var isEmpty: Bool {
        self.elements.isEmpty
    }
    
    /// O(1)
    public var count: Int {
        return elements.count
    }
    
    /// O(1)
    public var peek: T? {
        elements.first
    }
    
    // MARK: - initialization
    
    public init(sortFunction: @escaping (T, T) -> Bool) {
        self.sortFunction = sortFunction
    }
    
    // MARK: - Methods
    
    private func parentIndex(of i: Int) -> Int {
        return (i - 1) / 2
    }
    
    private func leftChildIndex(of i: Int) -> Int {
        return 2*i + 1
    }
    
    private func rightChildIndex(of i: Int) -> Int {
        return 2*i + 2
    }
    
    /// O(N)
    public func contains(_ item: T) -> Bool {
        return elements.contains(where: { $0 == item })
    }
    
    /// O(logN)
    mutating
    public func insert(_ item: T) {
        elements.append(item)
        swimUp(elements.count - 1)
    }
    
    /// O(logN)
    mutating
    private func swimUp(_ index: Int) {
        var childIndex = index
        let child = elements[childIndex]
        var parentIndex = self.parentIndex(of: childIndex)
        
        while childIndex > 0 && sortFunction(child, elements[parentIndex]) {
            elements[childIndex] = elements[parentIndex]
            childIndex = parentIndex
            parentIndex = self.parentIndex(of: childIndex)
        }
        
        elements[childIndex] = child
    }
    
    /// root 노드를 제거
    /// O(logN)
    @discardableResult
    public mutating func remove() -> T? {
        guard !elements.isEmpty else { return nil }
        
        if elements.count == 1 {
            return elements.removeLast()
        } else {
            let value = elements[0]
            elements[0] = elements.removeLast()
            diveDown(0)
            return value
        }
    }
    
    /// 특정 인덱스의 노드 제거
    /// O(logN)
    @discardableResult
    public mutating func remove(at index: Int) -> T? {
        guard index < elements.count else { return nil }
        let lastIndex = elements.count - 1
        elements.swapAt(index, lastIndex)
        diveDown(from: index, until: lastIndex)
        swimUp(index)
        return elements.removeLast()
    }
    
    /// O(1)
    public mutating func removeAll() {
        self.elements = []
    }
    
    /// O(logN)
    private mutating func diveDown(_ index: Int) {
        diveDown(from: index, until: elements.count)
    }
    
    /// O(logN)
    private mutating func diveDown(from index: Int, until endIndex: Int) {
        let leftChildIndex = leftChildIndex(of: index)
        let rightChildIndex = rightChildIndex(of: index)
        
        var temp = index
        
        if leftChildIndex < endIndex && sortFunction(elements[leftChildIndex], elements[temp]) {
            temp = leftChildIndex
        }
        
        if rightChildIndex < endIndex && sortFunction(elements[rightChildIndex], elements[temp]) {
            temp = rightChildIndex
        }
        
        if temp == index { return }
        
        elements.swapAt(index, temp)
        diveDown(from: temp, until: endIndex)
    }
}

Swift에는 기본적으로 Heap이나 Priority Queue가 없기 때문에 직접 구현해야 합니다..ㅠㅠ

 

 

2. Job 구조체 구현

fileprivate struct Job: Comparable {
    var inputTime: Int      // 작업이 요청되는 시점
    var requiredTime: Int   // 작업의 소요 시간
    
    static func < (lhs: Job, rhs: Job) -> Bool {
        if lhs.requiredTime == rhs.requiredTime {
            return lhs.inputTime < rhs.inputTime
        }
        
        return lhs.requiredTime < rhs.requiredTime
    }
    
    init(job: [Int]) {
        self.inputTime = job[0]
        self.requiredTime = job[1]
    }
}

Heap에는 Comparable 타입이 들어가야합니다.

따라서 각 작업을 객체로 만들어서 넣기 위해 Job 구조체를 생성했습니다.

 

Comparable 프로토콜을 채택하고 static func < (lhs:, rhs:)를 구현합니다.

requiredTime이 작은 쪽이 더 작은 객체로 판단되도록 했습니다. (requiredTime이 같다면 inputTime으로 비교)

 

3. solution 함수 구현

fileprivate func solution(_ jobs:[[Int]]) -> Int {
    var jobs = jobs.sorted(by: { $0[0] >= $1[0] })  // 작업 요청 시점을 내림차순으로 정렬 (시간 복잡도가 낮은 removeLast를 사용하기 위해)
    let count = jobs.count
    var currentTime = 0
    var heap = Heap<Job>(sortFunction: <)
    var totalTime = 0   // 각 작업이 요청부터 종료까지 걸린 시간들의 합
    
    while !heap.isEmpty || !jobs.isEmpty {
        while !jobs.isEmpty && jobs.last![0] <= currentTime {
            heap.insert(Job(job: jobs.removeLast()))
        }
        
        if let nextJob = heap.remove() {
            let endTime = currentTime + nextJob.requiredTime
            
            totalTime += endTime - nextJob.inputTime
            
            currentTime = endTime
        } else {    // Heap이 비어있다면 현재 시각에서 가장 가까운 작업을 찾아서 헤당 작업의 요청 시각으로 이동
            currentTime = jobs.last![0]
        }
    }
    
    return totalTime / count
}

우선 jobs를 작업 요청 시간을 기준으로 내림차순으로 정렬합니다.

현재 시각까지 요청된 작업들을 jobs 배열에서 하나씩 빼와야 하는데 오름차순으로 정렬되어 있으면 removeFirst를 사용해야 합니다. 하지만 removeFirst는 O(N)이기 때문에 O(1)인 removeLast를 사용하기 위해 내림차순 정렬을 했습니다.

(테스트케이스들이 기본적으로 오름차순으로 정렬되어 있지 않습니다. 따라서 reversed()를 사용하지 말고 직접 정렬해야 합니다.)

 

heap이나 jobs 배열이 하나라도 비어 있지 않은 경우 while문 블럭을 계속 실행하도록 했습니다.

 

현재 시각까지 요청 들어온 작업(Job)들을 heap에 넣습니다.

그리고 수행할 작업을 찾기 위해 heap.remove()를 실행합니다.

 

만약 heap이 비어있다면 런타임 에러가 발생하기 때문에 다음 작업을 heap에 넣기 위해 현재 시간을 남은 작업들 중에서 요청 시각이 가장 가까운 시각으로 이동시킵니다.

 

heap이 비어있지 않다면 정상적으로 heap.remove()가 실행되었을 것이고 이렇게 얻은 Job을 실행합니다.

Job을 실행한다는 것은 totalTime에 해당 작업의 요청부터 종료까지 걸린 시간을 더하고,

현재 시간에 해당 Job을 수행하는 데 걸린 시간을 더하는 것을 의미합니다.

 

모든 Job을 마치고 totalTime에 count를 나눈 값을 리턴합니다.

 

 

마무리

문제를 읽고 소요시간이 가장 작은 작업부터 실행해야 한다는 것을 빠르게 알아차려야 했습니다.

그다음에는 Job들을 저장할 적합한 자료 구조를 찾아야 했습니다. Heap이나 Priority Queue가 해당됩니다.

 

이후에는 구현 문제입니다. 시간을 관리하는 변수와 반복문을 적절하게 활용하여 문제를 해결하고자 했습니다!!