Swift ) 프로그래머스(Lv3) - 디스크 컨트롤러 (PriorityQueue)

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

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

안녕하세요 후르륵짭짭 입니다.

오늘은 우선순위 큐 문제를 들고 왔습니다...

사실 이 문제를 정확히 풀었는데,,,, 가져다 쓴 Heap 정렬이 잘 못 된거라 

헛수고를 너무 많이 했습니다,,,,

 

** 이진 정렬 **

여기에서는 Heap 구조체를 사용하지 않고 어떻게 하면 구현할 수 있을지 고민을 많이 했습니다.

그래서 생각한 것이 이진탐색을 사용하도록 했습니다.

이진 탐색을 하면 시간 복잡도가 O(logN) 만에 정렬을 완료 할 수 있습니다.

Heap 정렬이랑 같죠.

 

코드를 보도록 하겠습니다.

typealias sequence = (start : Int , time : Int)

func makeMAX(list : inout [sequence], element : sequence){
    
    var start = 0
    var end = list.count - 1
    
    if list.isEmpty {
        list.append(element)
        return
    }
    
    while start <= end {
        
        let mid = (start + end) / 2
        
        if list[mid].time < element.time {
            start = mid + 1
        }
        else{
            end = mid - 1
        }
        
    }
    
    list.insert(element, at: start)
    
}

이 코드는 MAXHeap 과 동일한 역할을 하는 이진정렬 알고리즘 입니다.

처음에 List가 비어 있다면 처음 값을 넣어줍니다.

그리고 List가 한개 이상 들어 있다면 이제 아래 처럼 이진 정렬을 해줍니다.

- 새로 들어온 값이 최대 값일 때

- 새로 들어온 값이 최소 값일 때

- 새로 들어온 값이 중간 값일 때

 

그리고 마지막 start 위치에 새로운 값을 배열에 넣어주면 됩니다.

 

- MIN 이진 정렬 -

func makeMIN(list : inout [sequence], element : sequence){
    
    var start = 0
    var end = list.count - 1
    
    if list.isEmpty {
        list.append(element)
        return
    }
    
    while start <= end {
        
        let mid = (start + end) / 2
        
        if list[mid].time < element.time {
            end = mid - 1
        }
        else{
            start = mid + 1
        }
    }
    
    list.insert(element, at: start)
    
}

 

이렇게 된다면 정렬을 마지게 된 것이고 맨 마지막 값이 최대 값 / 최소값을 가지게 됩니다.

비록 Heap 처럼 한번에 되는 것은 아니지만,,,,, 

Swift에서는 Heap 라이브러리가 없는 관계로 이게 최선일 것 같습니다 ㅠㅠ 

 

** 문제 해설 **

typealias sequence = (start : Int , time : Int)

func makeMIN(list : inout [sequence], element : sequence){
    
    var start = 0
    var end = list.count - 1
    
    if list.isEmpty {
        list.append(element)
        return
    }
    
    while start <= end {
        
        let mid = (start + end) / 2
        
        if list[mid].time < element.time {
            end = mid - 1
        }
        else{
            start = mid + 1
        }
    }
    
    list.insert(element, at: start)
    
}


func solution(_ jobs:[[Int]]) -> Int {
    
    var PriorityQueue : [sequence] = []
    var jobsIndex = 0
    
    let jobs = jobs.sorted { (lhs, rhs) -> Bool in
        
        if lhs[0] == rhs[0]{
            return lhs[1]<rhs[1]
        }
        
        return lhs[0] < rhs[0]
    }
    
    var currentTime = jobs[0][0]
        
    for (index, element) in jobs.enumerated(){
        
        if element[0] == currentTime {
            makeMIN(list: &PriorityQueue, element: (element[0],element[1]))
            jobsIndex = index + 1
        }
        
    }
    
    var answer = 0
    
    while !PriorityQueue.isEmpty {
        
        let minElement = PriorityQueue.removeLast()
        
        let totalTime = currentTime + minElement.time - minElement.start
        answer += totalTime
        currentTime = currentTime + minElement.time
                
        while jobsIndex < jobs.count && jobs[jobsIndex][0] <= currentTime {
            makeMIN(list: &PriorityQueue, element: ( jobs[jobsIndex][0] , jobs[jobsIndex][1] ))
            jobsIndex += 1
        }
        
        if PriorityQueue.isEmpty && jobsIndex < jobs.count {
            currentTime = jobs[jobsIndex][0]
            
            while jobsIndex < jobs.count && jobs[jobsIndex][0] <= currentTime {
                makeMIN(list: &PriorityQueue, element: ( jobs[jobsIndex][0] , jobs[jobsIndex][1] ))
                jobsIndex += 1
            }
            
        }
        
 
    }
    
    return answer / jobs.count
}

문제는 어렵지 않았습니다. (바보 같이 잘 못 된 Heap 정렬 알고리즘을 써서 오래걸렸지만 ㅠㅠ )

 

처음에 요청시간 순으로 정렬을 해주고, 동일한 요청 시간이라면 작업 시간이 작은 쪽이 먼저 오도록 정렬을 해줍니다.

 let jobs = jobs.sorted { (lhs, rhs) -> Bool in
        
        if lhs[0] == rhs[0]{
            return lhs[1]<rhs[1]
        }
        
        return lhs[0] < rhs[0]
    }
    

그리고 이제 처음 시작 하는 요청 값을 Heap에 넣어줍니다.

var currentTime = jobs[0][0]
        
    for (index, element) in jobs.enumerated(){
        
        if element[0] == currentTime {
            makeMIN(list: &PriorityQueue, element: (element[0],element[1]))
            jobsIndex = index + 1
        }
        
    }

이제 본격적으로 우선순위 큐를 사용해서 답을 도출할 것 입니다.

while !PriorityQueue.isEmpty {
        
        let minElement = PriorityQueue.removeLast()
        
        let totalTime = currentTime + minElement.time - minElement.start
        answer += totalTime
        currentTime = currentTime + minElement.time
                
        while jobsIndex < jobs.count && jobs[jobsIndex][0] <= currentTime {
            makeMIN(list: &PriorityQueue, element: ( jobs[jobsIndex][0] , jobs[jobsIndex][1] ))
            jobsIndex += 1
        }
        
        .
        .
        .
        
 }

최소값을 가진 것을 우선순위 큐에서 빼주고 

요청에서 종료까지 값을 구해줍니다. 

위의 사진을 보면 요청 시점에서 부터 현재 종료 까지 시간과 실행 시간 까지 더해주는 것을 알 수 있습니다.

이렇게 요청에서 종료까지의 시간을 구해주고 나서  현재 종료 시점 보다 작은 요청시간을 찾아서 

우선순위 큐에 넣어줘야 합니다. 

넣어줄 때, 사용했던 job은 사용하면 안되니깐 jobsIndex를 증가시켜줍니다.

 

그리고 마지막으로 요청 시간이 [[0,1], [10,1]] 이렇게 떨어져 있는 경우는

현재 시간을 다시 처음으로 요청된 시점으로 갱신 해줍니다.

그리고 다음 내용은 동일합니다 ㅎㅎㅎ

 if PriorityQueue.isEmpty && jobsIndex < jobs.count {
            currentTime = jobs[jobsIndex][0]
            
            while jobsIndex < jobs.count && jobs[jobsIndex][0] <= currentTime {
                makeMIN(list: &PriorityQueue, element: ( jobs[jobsIndex][0] , jobs[jobsIndex][1] ))
                jobsIndex += 1
            }
            
        }

 

사실 이문제에서 젤 중요했던 것은 Heap을 좀 더 간단하게 사용하는 것을 알았습니다

바로 이진검색 알고리즘!!!

꼭 알아두면 좋을 것 같습니다!