Skip to content

[Algorithm] 디스크 컨트롤러 #195

@hwangJi-dev

Description

@hwangJi-dev

💬 문제

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


💬 Idea

  • SJF(Shortest Job First) 알고리즘을 구현하는 문제이다.

    → 정렬을 통해서 우선순위가 높은 데이터를 배열의 끝으로 보내서 removeLast()를 수행하자.

  1. 처음에는 가장 먼저 도착한 작업 수행
  2. 이번 작업 수행하는 동안 도착하는 작업들을 작업 큐에 모으기
  3. 작업 큐에 도착한 작업 중 수행시간이 가장 짧은 작업을 꺼내 수행시키기
  4. 모든 작업을 처리할 때까지 2, 3 반복

💬 풀이

import Foundation

func solution(jobs:[[Int]]) -> Int {
    var sortedJobs = jobs.sorted(by: {
        if $0[0] == $1[0] {
            return $0[1] > $1[1]
        } else {
            return $0[0] > $1[0]
        }
    })
    var jobQueue: [[Int]] = [sortedJobs.removeLast()]
    var totalTime = 0
    var time = jobQueue.first![0]
    
    while !jobQueue.isEmpty {
        let now = jobQueue.removeLast()
        totalTime += abs(time - now[0]) + now[1]
        time += now[1]
        
        while !sortedJobs.isEmpty && sortedJobs.last![0] <= time {
            jobQueue.append(sortedJobs.removeLast())
        }
        jobQueue.sort(by: { $0[1] > $1[1] })
        
        if jobQueue.isEmpty && !sortedJobs.isEmpty {
            jobQueue.append(sortedJobs.removeLast())
            time += abs(time - jobQueue.last![0])
        }
    }
    
    return totalTime / jobs.count
}

Metadata

Metadata

Assignees

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions