문제 42587. 프로세스

문제 링크

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

프로그래머스

 

 

난이도 : Lv.2

 

문제 요약 설명

운영체제의 역할 중 하나는 컴퓨터 시스템의 자원을 효율적으로 관리하는 것입니다. 이 문제에서는 운영체제가 다음 규칙에 따라 프로세스를 관리할 경우 특정 프로세스가 몇 번째로 실행되는지 알아내면 됩니다.

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

 

현재 실행 대기 큐(Queue)에 있는 프로세스의 중요도가 순서대로 담긴 배열 priorities와, 몇 번째로 실행되는지 알고싶은 프로세스의 위치를 알려주는 location이 매개변수로 주어질 때, 해당 프로세스가 몇 번째로 실행되는지 return 하도록 solution 함수를 작성해주세요.

입력

• 현재 실행 대기 큐(Queue)에 있는 프로세스의 중요도가 순서대로 담긴 배열 priorities
• 몇 번째로 실행되는지 알고싶은 프로세스의 위치를 알려주는 location

입력 제한

• priorities의 길이는 1 이상 100 이하입니다.
  
  • priorities의 원소는 1 이상 9 이하의 정수입니다.
  • priorities의 원소는 우선순위를 나타내며 숫자가 클 수록 우선순위가 높습니다.
• location은 0 이상 (대기 큐에 있는 프로세스 수 - 1) 이하의 값을 가집니다.
  
  • priorities의 가장 앞에 있으면 0, 두 번째에 있으면 1 … 과 같이 표현합니다.

입력 예제

// input
[2, 1, 3, 2]	// priorities
2				// location

// ans
1

 

풀이 방식

이 문제는 데큐 자료구조를 사용하면 된다. 그냥 큐가 아닌 데큐인 이유는 데큐는 큐와 다르게 배열처럼 인덱스로 접근할 수 있기 때문이다. 현재 남아있는 프로세스들 중 가장 높은 우선 순위가 무엇인지 알기위해서는 인덱스에 접근할 수 있어야한다. 그렇기 때문에 데큐를 큐 대신 사용한 것이다.(물론 우선 순위에 대한 정보를 따로 저장한 다음 풀면 큐를 사용해도 된다.)

자료구조를 데큐로 정한 다음에는 크게 어려울 게 없다. 데큐에서 프로세스가 하나 빠질때마다 후에 가장 높은 우선순위의 값을 구해 저장하고 있으면 된다. 하나씩 확인해가며 현재 프로세스가 가장 높은 우선순위보다 낮으면 넘기고, 같다면 데큐에서 해당 값을 뺀다. 

이렇게 location에 해당하는 프로세스가 빠질때까지 반복하며 몇 번째로 실행되는 지 확인하면 정답이 나온다.

 

정답 코드 

#include <string>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

struct pos_data{
    int idx;
    int p;
};

int solution(vector<int> priorities, int location) {
    int answer = 0;
    
    deque<pos_data> dq;
    
    for(int i = 0; i < priorities.size(); i++){
        dq.push_back({i, priorities[i]});
    }
    
    int cnt = 0;
    bool find = false;
    while(!find){
        pos_data cur_proc = dq.front(); dq.pop_front();
        
        int max_p = -1;
        for(pos_data pd : dq){
            max_p = max(max_p, pd.p);
        }
        
        if(cur_proc.p < max_p){
            dq.push_back(cur_proc);
        }
        else{
            cnt++;
            if(cur_proc.idx == location) find = true;
        }
        
        if(find) break;
    }
    
    answer = cnt;
    
    return answer;
}