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

문제 풀이 아이디어: Heap

가장 적게 기다려야 한다!

작업이 걸리는 시간은 2가지 부분으로 나뉘어 있습니다. (요청 ~ 작업이 수행되기까지 대기하는 시간) + (작업을 수행하는 시간)입니다. 각각의 작업에서 작업을 실제 수행하는 시간은 fix 되어 있으니 우리가 조정할 수 있는 시간은 요청 ~ 작업이 수행되기까지 대기하는 시간입니다.

대기 시간을 줄이기 위해서는 현재 수행해야 하는 작업 중에서 (= 요청이 들어온 작업 중에서) 가장 짧은 수행 시간을 가진 작업을 먼저 수행해야 합니다. 즉 요청이 들어올 때마다 수행 시간을 기준으로 내림차순으로 정렬해야 합니다.

따라서 뭔가 새로 추가될 때마다 정렬이 필요할 때 사용하는 자료구조인 Heap을 사용하는 것이 가장 좋습니다. 만약에 그냥 Array를 사용한다면 정렬할 때마다 O(nlogn)의 시간복잡도를 가지지만 Heap을 사용한다면 정렬 1회를 O(logn)으로 수행할 수 있습니다.

주의할 점

1. “하드디스크가 작업을 수행하지 않을 때는 먼저 들어온 요청부터 처리합니다.”라는 조건이 있습니다. 따라서 나중에 들어올 작업이 짧은 작업이라고 기다리거나 할 수 없습니다.
2. jobs가 정렬이 되어 있다는 얘기는 없습니다. 정렬부터 하고 시작합니다.
3. 중간에 하드디스크가 작업하지 않는 시간이 있을 수 있습니다. (= 다음 작업의 요청 시간이 아직 안되어서) 이 경우에는 요청 시간에 현재 시간을 맞추고 요청 작업을 push 해야 합니다.

힙을 구현하는 방법

힙을 구현하는 방법에 대해서는 이 포스팅에서는 설명 하지 않겠습니다. 이 포스팅을 참고 해주세요!

코드

// 최소힙 구현
import Foundation

struct MinHeap {
    var heap: [[Int]] = []

    var isEmpty: Bool {
        return heap.count <= 1 ? true : false
    }
    
    
    init() {}

    init(_ element: [Int]) {
        heap.append(element)
        heap.append(element)
    }
    
    mutating func insert(_ element: [Int]) {
        
        if heap.isEmpty {
            heap.append(element)
            heap.append(element)
            return
        }
        
        heap.append(element)
        
        func isMoveUp(_ insertIndex: Int) -> Bool {
            if insertIndex <= 1 {
                return false
            }
            
            let parentIndex = insertIndex / 2
            return heap[insertIndex][1] < heap[parentIndex][1] ? true : false
        }
        
        var insertIndex = heap.count - 1
        
        while isMoveUp(insertIndex) {
            let parentIndex = insertIndex / 2
            heap.swapAt(insertIndex, parentIndex)
            insertIndex = parentIndex
        }
    }
    

    enum moveDownDirection { case left, right, none }
    

    mutating func pop() -> [Int]? {
        
        if heap.count <= 1 {
            return nil
        }
        
        let returnData = heap[1]
        heap.swapAt(1, heap.count - 1)
        heap.removeLast()
        
        func moveDown(_ poppedIndex: Int) -> moveDownDirection {
            
            let leftChildIndex = poppedIndex * 2
            let rightChildIndex = leftChildIndex + 1
            
            if leftChildIndex >= heap.count {
                return .none
            }
            
            if rightChildIndex >= heap.count {
                return heap[leftChildIndex][1] < heap[poppedIndex][1] ? .left : .none
            }
            
            if (heap[leftChildIndex][1] > heap[poppedIndex][1]) && (heap[rightChildIndex][1] > heap[poppedIndex][1]) {
                return .none
            }
            
            if (heap[leftChildIndex][1] < heap[poppedIndex][1]) && (heap[rightChildIndex][1] < heap[poppedIndex][1]) {
                return heap[leftChildIndex][1] < heap[rightChildIndex][1] ? .left : .right
            }
            
            if (heap[leftChildIndex][1] < heap[poppedIndex][1]) || (heap[rightChildIndex][1] < heap[poppedIndex][1]) {
                return heap[leftChildIndex][1] < heap[rightChildIndex][1] ? .left : .right
            }
            
            return .none
        }
        
        var poppedIndex = 1
        while true {
            switch moveDown(poppedIndex) {
            case .none:
                return returnData
            case .left:
                let leftChildIndex = poppedIndex * 2
                heap.swapAt(poppedIndex, leftChildIndex)
                poppedIndex = leftChildIndex
            case .right:
                let rightChildIndex = (poppedIndex * 2) + 1
                heap.swapAt(poppedIndex, rightChildIndex)
                poppedIndex = rightChildIndex
            }
        }
    }
}

func solution(_ jobs:[[Int]]) -> Int {
   
    // 작업을 시작 시간 역순으로 정렬 (마지막 element를 pop 해야지 O(1)이므로)
    var sortedJobs = jobs.sorted { $0[0] > $1[0] }
    // 현재 지난 시간
    var time = 0
    // 최소힙
    var heap = MinHeap()
    // 각 작업의 요청 ~ 끝 시간의 합
    var cost = 0
    
    // 힙이 비어 있거나 (대기중인 작업 없음) or 정렬된 작업이 빈 경우 (요청할 작업 없음) 반복문 종료
    while !(heap.isEmpty && sortedJobs.isEmpty) {
        // 요청 대기 중인 작업 중에서 요청 시간이 현재 시간 이하인 작업들을 push
        while !sortedJobs.isEmpty && sortedJobs.last![0] <= time {
            heap.insert(sortedJobs.popLast()!)
        }

        // 만약에 힙이 비었다면 (대기 중인 작업이 없는 경우 = 아직 요청 시간이 안되서 요청할 작업이 요청이 안된 경우)
        if heap.isEmpty {
            // 가장 이른 요청 시간까지 시간을 맞춘다.
            time = sortedJobs.last![0]
            continue
        }
        
        // 현재 작업
        var now = heap.pop()!
        
        // 현재 작업에 걸리는 시간만큼 시간을 더하고
        time += now[1]
        // 요청 ~ 끝 시간을 cost에 더한다.
        cost += time - now[0]
        
    }
    
    // 요청 ~ 끝의 평균값을 리턴한다.
    return cost / jobs.count
}