[STACK]프로세스

 

문제

 

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

 

개념화

 

출력)
location 프로세스가 몇번째로 실행되는지?

<작업 내용>

 

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

1) pair 변수 선언.
2) 작업 순서대로 작업 진행. // 첫번째 : 1
 -> 작업 배열 내에 자신보다 큰 우선순위가 있는지 확인 =
    => 있으면 다시 push_back.
    => 없으면 pop_front && 작업 순번 증가.
3) 현재 완료된 작업의 location과 입력 location 비교
4) 동일할시 현재 작업된 순번return.
5) 배열이 모두 삭제될때까지 동작 진행.

 

코드

#include <vector>
#include <algorithm>
#include <queue>
#include <iostream>

using namespace std;

int solution(vector<int> priority,int location)
{
    deque<pair<int,int>> works;
    int sequance=1;
    //pair 선언
    for(int i=0;i<priority.size();i++)
    {
        works.push_back({i,priority[i]});
    }

    while(!works.empty())
    {
        auto cur_work =works.front();
        works.pop_front();
        int first_priority = *max_element(priority.begin(),priority.end());

        if(cur_work.second<first_priority) // 우선순위 밀림
        {
            works.push_back(cur_work); // 뒤로 다시 넣기.
        }
        else // 우선순위 최고
        {
            // vector에서 최댓값 삭제.
            priority.erase(find(priority.begin(), priority.end(), first_priority));

            if (cur_work.first == location) // 현재 작업이 요청순서와 동일하다면
            {
                return sequance; // 현재 작업순서 리턴.
            }
            sequance++;
        }
    }

    return priority.size();
}

 

 

추가적으로 알게 된 내용

 

0) 존재하는 배열내에서 가장 우선순위가 높은 값 찾는방법.

 

 

** 결론

 - 특정 조건을 구현 가능한 가장 쉬운 방식으로 구현하자.

 - 만약 현재 사용하고 있는 컨테이너로 해당 방법이 구현 불가능하다면 새로운 컨테이너를 선언 및 사용하여 문제 풀이가 가능하다.

 

2차로 문제풀이중 문제가 발생했다. 개념화를 정확하게 수행했지만, 우선순위를 찾을때 문제가 발생했다.

우선, deque<pair<>>를 사용하여 순번과 우선순위 변수를 선언하였다.

 

두번째로 현재 우선순위가 전체 배열에서 가장 높은 우선순위를 갖는지 확인해야했다.

이때, 보통 컨테이너 내부의 가장 높은 값을 찾는 방법은 *max_element() 메서드를 사용하여 찾지만, deque<pair<>>에서는 해당 동작이 불가능하다.

 

따라서 deque 배열을 순회하며 max값을 찾아내었고 해당값과 현재 우선순위값이 같은지 비교하여 같다면 최대 우선순위라 판단하여 실행하도록 구현하였다.

 

문제는 현재 배열을 제외한 상태에서 순회하여 max값을 찾아내었기에 현재 배열이 가장 높은 우선순위를 갖는다면 계산한 최대값보다 현재값이 크기때문에 무한 루프에 들어가게 된다(계속해서 현재값을 뒤에 push 해주기 때문)

 

따라서 우선순위를 판단할때, 이미 존재하는 priorities 컨테이너와 *max_element 메서드를 활용하여 찾는 것이 더 효율적이다.

 

 

 

#위의 이슈사항이 발생했던 2차 코드

#include<iostream>
#include <vector>
#include <stack>
#include <queue>

using namespace std;

int solution(vector<int> priorities,int location)
{
    deque<pair<int,int>> dq;
    int idx=1;

    for(int i=0;i<priorities.size();i++)
    {
        dq.push_back({i,priorities[i]});
    }

    while(!dq.empty())
    {
        auto [seq_cur , prior_cur] = dq.front();
        dq.pop_front();
        bool is_prior=true;
        int max =0;

        for(auto [seq , prior] : dq)
        {
            if(max<prior)
            {
                max=prior;
            }
        }

        if(prior_cur>=max)
        {
            if(seq_cur==location)
                break;
            idx++;
        }
        else
        {
            dq.push_back({seq_cur,prior_cur});
        }
    }

    return idx;
}