[PS] 프로세스

문제

프로그래머스

우선순위 배열 내의 특정 위치에 있는 프로세스의 실행 순서 계산하기

 

 

풀이

현재 내가 pop하려는 수보다 더 큰 수가 큐 내에 없다면 그대로 pop한다는 규칙이 있다.

그렇다면, 더 큰 수가 있는지 없는지 체크하는 조건문이 있어야 한다.

이를 어떻게 구현할 수 있을까?

크게 두 가지로, (1)큰 우선순위를 가지는 프로세스와 비교하여 (2)해당 프로세스가 현재 pop가능한지 체크한다.

pop 가능하다면 pop 횟수를 증가시키고, 불가능하다면 그대로 다시 배열에 넣어준다.

 

1. 큰 우선순위를 가지는 프로세스

우선순위를 가지므로 간단하게 우선순위 큐를 이용하여 풀이하면 된다.

입력받은 배열을 우선순위 큐에 저장하면 자동으로 우선순위 별로 정렬이 되며,

이때의 배열의 순서가 프로세스가 pop되는 순서이다.

 

2. 해당 프로세스가 현재 pop 가능한지 체크

현재 내가 pop하려는 수가 가장 큰 우선순위를 가지는 프로세스라면 pop할 수 있다.

가장 큰 우선 순위를 가지는 프로세스는 우선순위 큐의 top이고,

또 따로 큐를 만들어서 이와 비교하면 된다.

 

그렇다면 정답은 어떻게 구할까?

location 위치에 있는 프로세스의 실행 순서를 계산해야 하므로,

인덱스를 저장하는 큐도 따로 만들어서 pop 할 때의 인덱스가 location과 동일하다면 바로 return한다.

 

코드

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(vector<int> priorities, int location) {
    int answer = 0;
    queue<int> Process;
    queue<int> Location;
    priority_queue<int> Priority;
    
    // 우선순위대로 큐에 넣기
    for (int index = 0; index < priorities.size(); index++){
        Process.push(priorities[index]);
        Location.push(index);
        Priority.push(priorities[index]);
    }
    
    // priorities[location]의 수가 몇 번째에 pop() 되는지 알아야 한다
    // 인덱스를 쫓는 큐를 하나 더 만들어서, 지금 pop하는 인덱스가 location이면
    // 이 때의 answer가 정답
    while(!Process.empty()){
        int process_front = Process.front(); Process.pop();
        int process_index = Location.front(); Location.pop();
        int priority_front = Priority.top(); Priority.pop();
        
        // 현재 큐의 front가 pop 가능한지 체크
        if (process_front < priority_front){
            // pop 불가능, 다시 큐에 넣기
            Process.push(process_front);
            Location.push(process_index);
            Priority.push(priority_front);
        } else {
            // pop 가능, pop 횟수 증가
            answer++;
            
            // 현재 pop한 수가 몇 번째로 실행되는지 알고 싶은 프로세스의 위치와 동일하다면, 현재의 answer를 반환
            if (process_index == location)
                return answer;
        }
    }
}

 

회고

pair로 쌍을 만들어서 인덱스를 저장해도 된다.

나중에 이 방식으로 풀어보면 더 실력이 늘 것 같다.