[고득점 Kit(힙)] 디스크 컨트롤러 (Swift, Python)

 

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

 

풀이

 먼저 입력으로 주어진 jobs에 대해서 작업이 요청되는 시점순으로 정렬하고 작업이 요청되는 시점이 같다면 작업의 소요시간을 기준으로 오름차순으로 정렬한다. 현재 시간 이전에 요청된 작업들을 toDoJobs 힙에 넣어주고 작업 소요시간이 가장 짧은 작업을 먼저 수행한다. 그 후 다시 현재 시간에 수행할 수 있는 작업들을 찾아서 toDoJobs 힙에 넣어주고 다시 작업 소요시간이 가장 짧은 작업을 수행한다.

 

 위와 같은 작업을 반복한 뒤 입력으로 주어진 jobs 배열에 더 이상 값이 없으면 마지막으로 toDoJobs에서 작업 소요시간이 짧은 작업 순으로 작업을 마친뒤 계산한 걸린 시간의 평균을 return 해주면 된다.

 

코드

[Swift]

import Foundation

var time: Int = 0 // 현재 시간
var toDoJobs: [[Int]] = [] // 현재 시간에서 수행할 수 있는 작업들

// toDoJobs에 담긴 작업들을 수행하기 위한 메서드
func doTask() -> Int {
    // 현재 시간에 수행할 수 있는 작업이 없을 경우에는 0을 return
    if toDoJobs.count == 0 {
        return 0
    }
    
    toDoJobs.sort(by: jobsSort) // 작업 소요시간, 작업이 요청되는 시점 순으로 정렬
    let process = toDoJobs.removeFirst()
    let totalTime = time - process[1] + process[0] // 현재 수행할 작업의 요청부터 종료까지의 시간 계산
    time += process[0] // 현재 시간 업데이트
    
    return totalTime
}

func solution(_ jobs:[[Int]]) -> Int {
    let taskCount = jobs.count
    var sortedJobs = jobs.sorted(by: jobsSort) // 입력으로 주어진 작업들을 정렬
    var answer: Int = 0
    
    while true {
        // 현재 수행할 수 있는 작업이 없고 현재 시간이 다음으로 수행할 작업의 요청 시간보다 이전일 경우
        // 현재 시간을 해당 작업의 요청 시간으로 변경
        if toDoJobs.isEmpty && sortedJobs.count != 0 && time < sortedJobs[0][0] {
            time = sortedJobs[0][0]
        }
        
        // 현재 시간 이전에 요청된 작업들을
        // 수행할 수 있는 작업 목록에 추가
        while sortedJobs.count != 0 && sortedJobs[0][0] <= time {
            let process: [Int] = sortedJobs.removeFirst()
            let startTime: Int = process[0]
            let takenTime: Int = process[1]
            toDoJobs.append([takenTime, startTime])
        }
        
        // 작업 수행
        answer += doTask()
        
        if sortedJobs.count == 0 {
            break
        }
    }
    
    // 나머지 수행할 수 있는 작업들 수행
    while !toDoJobs.isEmpty {
        answer += doTask()
    }
    
    return answer / taskCount
}

func jobsSort(lhs: [Int], rhs: [Int]) -> Bool {
    if lhs[0] == rhs[0] {
        return lhs[1] < rhs[1]
    }
    return lhs[0] < rhs[0]
}

 

[Python]

import heapq

toDoJobs = [] # 현재 시간에서 수행할 수 있는 작업들

# toDoJobs에 담긴 작업들을 수행하기 위한 메서드
def doTask():
    global time

    # 현재 시간에 수행할 수 있는 작업이 없을 경우에는 0을 return
    if len(toDoJobs) == 0:
        return 0

    takenTime, startTime = heapq.heappop(toDoJobs)
    totalTime = time - startTime + takenTime # 현재 수행할 작업의 요청부터 종료까지의 시간 계산
    time += takenTime # 현재 시간 업데이트

    return totalTime


def solution(jobs):
    global time
    taskCount = len(jobs)
    jobs.sort() # 입력으로 주어진 작업들을 정렬
    answer = 0
    time = 0 # 현재 시간

    while True:
        # 현재 수행할 수 있는 작업이 없고 현재 시간이 다음으로 수행할 작업의 요청 시간보다 이전일 경우
        # 현재 시간을 해당 작업의 요청 시간으로 변경
        if len(toDoJobs) == 0 and jobs and time < jobs[0][0]:
            time = jobs[0][0]

        # 현재 시간 이전에 요청된 작업들을
        # 수행할 수 있는 작업 목록에 추가
        while jobs and jobs[0][0] <= time:
            startTime, takenTime = jobs.pop(0)
            heapq.heappush(toDoJobs, (takenTime, startTime))

        # 작업 수행
        answer += doTask()

        if len(jobs) == 0:
            break
        
    # 나머지 수행할 수 있는 작업들 수행
    while toDoJobs:
        answer += doTask()

    return answer // taskCount