[프로그래머스/Lv.2 (Swift)] 우선순위 큐

스택/큐 > 프로세스

 

 

해당 문제는 우선순위 큐 관련 문제입니다.

 

1. 실행 대기 큐(Queue)에서 대기중인 프로세스 하나를 꺼냅니다.
2. 큐에 대기중인 프로세스 중 우선순위가 더 높은 프로세스가 있다면 방금 꺼낸 프로세스를 다시 큐에 넣습니다.
3. 만약 그런 프로세스가 없다면 방금 꺼낸 프로세스를 실행합니다.
3.1 한 번 실행한 프로세스는 다시 큐에 넣지 않고 그대로 종료됩니다.

(스택/큐 > 프로세스)

 

 

 

우선순위 큐(Priority Queue)는

우선순위가 높은 작업부터 먼저 처리되는 큐입니다.

 

 

 

해당 문제는 위와 같이 큐 안에 값들이 들어와 있을 때,

 

입력받은 인덱스에 해당하는 작업이

몇 번째에 실행될지를 아는 것이 목적입니다.

 

---

 

 

여기서 중요한 점은

내가 뽑은 값보다 우선순위가 높은 값이 존재한다면

이 값을 처리하지 못하고 맨 뒤로 보내야 한다는 점입니다.

 

 

 

내가 뽑은 값보다 우선순위가 높은 값이 존재

 

이를 트래킹하기 위해선, 

가장 큰 우선순위를 가지고 있는 변수 하나를 지정할 수 있습니다.

 

 

 

해당 우선순위들을 큰 순서대로 정렬하고,

현재 가장 높은 우선순위를 가리키는 변수 값을 만듭니다.

 

 

흐름을 나타내면 다음과 같습니다.

 

 

 

 

---

import Foundation

func solution(_ priorities:[Int], _ location:Int) -> Int {
    
    var queue = priorities.enumerated().map { ($0, $1) } // 인덱스, 해당 우선순위 값
    var result = 0
    
    var priorityOrder = priorities.sorted { $0 > $1 }   // 작업 우선 순위대로 정렬
    var currentPriorityIndex = 0    // 현재 이 중에서 제일 높은 값을 가지고 있는 것의 인덱스
        
    while !queue.isEmpty {
        // queue에서 값을 하나 꺼내옴
        var current = queue.removeFirst()
        
        // 만약 꺼낸 값이 현재 우선순위의 값보다 작다면
        // 다시 뒤로 보냄
        if current.1 < priorityOrder[currentPriorityIndex] {
            queue.append(current)
        } else {
            // 만약 만족한다면
            result += 1
            currentPriorityIndex += 1
            
            // 내가 찾는 그 값인가?
            if current.0 == location {
                return result
            }
        }
    }
    
    return result
}