프로그래머스 - 프로세스

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

프로그래머스

 

 

 

 

간단하게 정리하면

실행 대기 큐에 각각 우선순위가 있는 프로세스가 있는데

프로세스를 하나 꺼냈을 때, 우선순위가 제일 높지 않다면 다시 큐에 넣고

제일 높은 우선순위를 가진다면 실행한다

이때, 특정 프로세스가 몇 번째로 실행되는지를 구하는 문제이다

가장 먼저 든 생각은

큐에서 프로세스를 꺼냈다가 다시 넣는 과정에서 처음 인덱스를 어떻게 구분할까? 라는 생각이 먼저 들었다

우선순위가 담긴 배열에서 pop하고 append하는 과정을 거치면 index 번호가 변경되므로 이를 해결할 방법이 필요했다

이를 (처음 인덱스, 우선순위) 튜플 형식으로 해결하고자 했다

예를들어 현재 우선순위 배열이 [2, 1, 3, 2] 일 때 [(0, 2), (1, 1), (2, 3), (3, 2)] 이처럼 처음 인덱스 번호를 따로 저장하도록 구현하고 후에 location과 비교할 수 있도록 했다

1. 큐의 앞에서부터 프로세스를 꺼내고
2. 꺼낸 프로세스의 우선 순위가 남은 큐에서 가장 높은 우선순위보다 높은지 확인
3. 꺼낸 프로세스가 가장 높은 우선순위라면 location과 해당 튜플의 첫 번째 값(처음 인덱스)과 같은지 확인
   • 같다면 종료 후 순서 리턴
   • 다르다면 큐에서만 제거하고 다시 반복문을 돌림
4. 꺼낸 프로세스의 우선순위가 높은 우선 순위가 아니라면, 다시 큐의 맨 뒤에 삽입

 

 

첫 번째 시도

import Foundation

func solution(_ priorities:[Int], _ location:Int) -> Int {
    var queue = priorities.indices.map{($0, priorities[$0])} // (처음 인덱스, 우선순위) 튜플 배열로 변경
    var answer = 1 // 실행 순서
    
    while !queue.isEmpty { // 큐에 프로세스가 없을 때까지 반복
        let current = queue.removeFirst() // 1. 첫번째 프로세스 추출
        guard let maxPriority = queue.map{$0.1}.max() else { break } // 2. 큐에 남은 프로세스 중 높은 우선순위 확인
        if current.1 >= maxPriority { // 2, 가장 높은 우선순위인지 확인
            if current.0 == location { break } // 3. 처음 인덱스가 location과 같은지 확인
            answer += 1 // location과 다르면 실행
        } else {
            queue.append(current) // 4. 가장 높은 우선 순위가 아니라면 다시 삽입
        }
    }
    
    return answer
}

→ 문제는 통과가 되었지만, 남은 큐에서 가장 높은 우선순위를 구하는 방법이 찝찝했다

 

매 반복마다 queue의 우선순위 최고값을 구해야하므로 시간복잡도가 증가할 것이다

큐의 우선순위만 따로 관리하는 배열을 만들어 정렬해두면 가장 높은 우선순위를 구할 때 큐를 탐색할 필요가 없어 시간을 줄일 수 있을 거 같았다

 

 

두 번째 시도

import Foundation

func solution(_ priorities:[Int], _ location:Int) -> Int {
    var queue = priorities.indices.map{($0, priorities[$0])}
    var sortedPriorities = priorities.sorted() // 우선순위만 관리하는 배열 추가
    var answer = 1
    
    while !queue.isEmpty {
        let current = queue.removeFirst()
        guard let maxPriority = sortedPriorities.last else { break } // 정렬되어 있으므로 마지막 값이 가장 큼
        if current.1 >= maxPriority {
            if current.0 == location { break }
            sortedPriorities.removeLast() // 큐에서 추출한 프로세스가 가장 우선순위가 큰 것이므로 마지막 값과 같을 거임
            answer += 1
        } else {
            queue.append(current)
        }
    }
    
    return answer
}

 

→ 확실하게 실행 시간이 감소되었다