[Programmers]#Level2_프로세스, 큐, 우선순위 큐

 

#1. 문제

 

프로그래머스

 

---

 

#2. 풀이

 

1. 큐

 

[자료 구조]#0_선형 자료구조

 

큐는 선입선출 방식으로 동작하는 선형 자료구조입니다. 큐는 동일한 형식의 데이터 항목을 목록의 한쪽 끝으로 삽입하며, 다른 한쪽에선 삭제 작업을 수행합니다. 

 

2. 우선순위 큐

 

[자료구조]#7_우선순위 큐

 

우선순위 큐는 원소들이 우선순위에 따라 정렬된 연결 자료구조로, 원소의 삽입 순서와 무관하게 우선순위가 가장 높은 원소가 먼저 나오는 특징을 갖고 있습니다. 우선순위 큐는 삽입/삭제 수행 시 내부적으로 정렬 작업을 수행하여 항상 정렬된 상태를 유지합니다. 이를 위해, 우선순위 큐는 일반적으로 '힙' 자료구조를 통해 구현합니다.

 

3. 가장 우선순위 높은 프로세스가 나올 때까지 기다리자!) 

 

1. 먼저, pair 형식(프로세스의 위치/Index, 프로세스의 우선순위)형식의 큐와 각 프로세스의 우선순위 번호를 관리하는 우선순위 큐를 하나 선언하고, 구성합니다.
2. 우선순위 큐를 순회하며, 우선순위가 가장 높은 프로세스를 찾을 때까지 큐의 pop연산+push연산을 반복해 줍니다. 이때, 우선순위 큐의 top(현재 우선순위가 가장 높은)과 큐의 front(현재 차례가 온 프로세스)의 우선순위가 동일한 와중에, 우리가 찾고자 하는 location 값 또한 해당 값들과 일치하는 삼위일체 발생 시 그 순서를 출력합니다!

 

---

 

#3. 코드

 

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

using namespace std;

int solution(vector<int> priorities, int location) {

    priority_queue<int, vector<int>> pq;
    queue<pair<int, int>> q;
    int answer = 0;
    int order = 1;

    for(int i=0; i < (int)priorities.size(); ++i)
    {
        pq.push(priorities[i]);
        q.push({i, priorities[i]});
    }

    while(!pq.empty())
    {
        int prior = pq.top();
        pq.pop();

        while(!q.empty() && q.front().second != prior)
        {
            q.push(q.front());
            q.pop();
        }
        if(q.front().first == location)
        {
            answer = order;
            break;
        }
        q.pop();
        order++;
    }

    return answer;
}

 

---