[Swift Algorithm] 42627 디스크 컨트롤러 (프로그래머스)

programmers.co.kr/learn/courses/30/lessons/42627

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

주어진 요청에따라 응답하는데 걸리는 최소평균시간을 구하는 문제에요

 

문제를 보면

아래처럼 요청이 들어와요

 

이러한 요청을 처리하는 다양한 방법이있죠

왼쪽처럼 처리하면 3 + 7 + 17 = 27ms

오른쪽처럼 처리하면 3 + 11 + 16 = 30ms

 

왼쪽처럼 하는 방법이 최선의 선택이겟네요!

 

풀이방법

우선순위 큐를 사용해서 해결 할 수 있는 문제에요

우선순위 큐는 힙자료구조를 사용하구요

 

간단하게 로직을 요약하면

우선 요청시간 순서대로 정렬을하고

요청시간이 같다면 처리시간이 작은순서대로 정렬하는게 포인트에요

 

처리시간을 작은순서대로 정렬하면 전체실행 시간이 최소가 될거에요

SJF알고리즘(최소작업우선 알고리즘)방식이죠

 

예시로 [0, 10], [0, 4]. [1. 5] 가 주어졌다면

요청시간이 빠르고 처리시간이 적은 [0,4] 부터 시작해요

처리를하고나면 4초에 끝나겟네요

 

그 다음에 [0,10], [1,5]를 비교할때 지금은 4초니까

이미 2개의작업은 언제든지 시작할 수 있는 위치에 놓여있어요

따라서 이땐 처리시간이적은 [1,5]를 선택해서 작업을 먼저하고

마지막으로 [0,10]을 선택해요

 

여기서 중요한것은

현 게시글을 작성하는 시점인

Swift5.3에는

Heap과 Priority Queue자료구조가 없어요!

직접 구현해야하죠

 

2021.03.29 - [iyOmSd/Title: Data Structure] - [Data Structure] Priority Queue 우선순위 큐

구현을 했다면

 

아래의 코드를 보면서 자세히 설명할게요

우선순위큐에는 현재시간에 맞는 실행 가능한 작업만 넣어줄거에요

 

1. 주어진 배열을 시작시간순서대로 정렬

 

2. 처음시작 시간이 0초가아니라면 모든 시작시간을 처음시작시간만큼 빼서 저장

이해를 돕기위해 [1,3], [4,2]가 요청으로 주어지면

1~4(요청1) 4~6(요청2) 의 소요시간으로 5초를 써야하므로

0초부터 계산하는게아니라 1초부터 계산을해야해요

1초부터시작하니가 전체시작시간을 1초를 빼줘서

요청을 [0,3], [3,2]로 변환처리해주는거에요

 

3. 우선순위 큐를 만들어주고 정렬순서는 처리시간이 짧은순이에요

힙정렬을 이용해서

요소를 넣고 뺄때 재 정렬이 일어나죠

 

4.우선순위 큐(작업해야할 대기목록) 이 있거나 아직 작업을 끝까지 보지않은경우에 반복문이 돌아가고

 

5. 현재시간과 작업의 시작시간을 비교해서 현재시간에 시작할 수 있는 모든 작업들을 우선순위 큐에 넣어줘요

 

6. 우선순위큐에서 하나를 빼내서 응답시간을 더해주고 현재시간을 변경해줘요

작업의 응답시간 = 현재시간 - 작업의시작시간 + 처리시간 이죠

현재시간 - 작업시작시간 -> 대기시간

 

현재시간에 맞는 작업들을 큐에 넣어주고 하나씩 빼서 더해주면 성공할 수 있어요

private func solutionP42627(_ jobs:[[Int]]) -> Int {
    
    struct Disk {
        var start: Int
        let process: Int
    }
    
    var jobs = jobs.map { Disk(start: $0[0], process: $0[1]) }
    jobs.sort { $0.start < $1.start }
    
    let firstTime = jobs[0].start
    if firstTime != 0 {
        for i in jobs.indices {
            jobs[i].start -= firstTime
        }
    }
    
    var priorityQueue = PriorityQueue<Disk> {
        if $0.process == $1.process {
            return $0.start < $1.start
        } else {
            return $0.process < $1.process
        }
    }
    
    var curTime = 0
    var totalTime = 0
    var jobsIndex = 0

    while jobsIndex < jobs.count || !priorityQueue.isEmpty() {
    
        while jobsIndex < jobs.count && jobs[jobsIndex].start <= curTime {
            priorityQueue.enQueue(jobs[jobsIndex])
            jobsIndex += 1
        }
        
        if let disk = priorityQueue.deQueue() {
            totalTime += curTime - disk.start + disk.process
            curTime += disk.process
        } else {
            curTime = jobs[jobsIndex].start
        }

    }
    
    let result = totalTime/jobs.count
    return result
}
//solutionP42627([[0, 3], [4, 3], [10, 3]])  //3
//solutionP42627([[0,10],[2,3],[9,3]]) // 9
//solutionP42627([[0,10]]) // 10
//solutionP42627([[1,10], [3,3], [10,3]]) // 9