프로세스 / deque 활용

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

 

문제에서 제시한 프로세스 그대로 구현하려고 생각했다.

queue의 앞 요소를 꺼내와 현재 대기중인 프로세스 중, 우선순위가 더 높은 프로세스가 있다면 다시 뒤에다가 넣어야 했는데 앞과 뒤의 삽입/삭제가 빈번하다면 O(1)의 속도를 가지고 있는 deque를 사용하는게 효율적이라고 판단했다.

그리고 우선순위가 더 높은 프로세스가 있는지 확인하려면 두 가지 방법이 있다.

첫 번째로는 algorithm 헤더의 max_element를 사용하여 현재 priorites 배열의 max 값보다 queue의 top 요소가 작은지 큰지를 비교하고 크거나 같다면 max 값을 0으로 바꿔 갱신하는 방법이 있는데, 매 루프마다 이 값을 연산해서 확인하는 것은 시간 복잡도 면에서 비효율적이라고 생각했다.

두 번째 방법은 priority_queue, max heap을 사용해 최대 값을 정렬해놓고 바로바로 지우는 것이다. 이 방법이 메모리는 더 사용할 수 있지만 시간 복잡도 면에서 더 효율적이라고 판단해 두 번째 방법으로 구현하였다.

 

 

✅ 구현 코드

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

using namespace std;

int solution(vector<int> priorities, int location)
{
	// 앞과 뒤의 삽입/삭제 효율을 위해 deque 선언
	deque<pair<int, int>> dq;
    // 최대 값 빠른 비교를 위해 max heap 선언
	priority_queue<int> max_heap;
    
    // 초기화 작업
	for (int i = 0; i < priorities.size(); i++)
	{
		dq.push_back({ i, priorities[i] });
		max_heap.push(priorities[i]);
	}
	
	int answer = 0;
	while (!dq.empty())
	{
		auto temp = dq.front();
		dq.pop_front();
		
        // 현재 최대 값 보다 작으면 deque에 뒤에 삽입
		if (temp.second < max_heap.top())
		{
			dq.push_back(temp);
		}
        // 현재 최대 값과 같거나 작다면 answer(프로세스 실행 순서) 증가 및 최대 값 갱신
        // 만약 현재 인덱스가 location과 같다면 현재의 answer 값 return
		else
		{
			answer++;
			max_heap.pop();
			
			if (temp.first == location)
			{
				return answer;
			}
		}
	}
	
	return -1;
}