(프로그래머스) 프로세스

문제 링크

• 프로그래머스

요약

• 하라는대로 하면 된다.

최종 §

결과

• 그냥 지문에 나온대로 하면 된다.

#include <string>
#include <vector>
#include <queue>
#include <map>
 
using namespace std;
 
struct Proc {
	int idx;
	int priority;
};
 
int solution(vector<int> priorities, int location) {
	queue<Proc> q;
	map<int, int> tbl;
	int step = 0;
	
 
	for (int i = 0; i < priorities.size(); i++) {
		q.push({i, priorities[i]});
		tbl[priorities[i]]++;
	}
 
	while (!q.empty()) {
		Proc cur = q.front();
		q.pop();
 
		if (cur.priority == tbl.rbegin()->first) {
			step++;
 
			if (cur.idx == location) {
				return step;
			}
 
			tbl[cur.priority]--;
 
			if (!tbl[cur.priority]) {
				tbl.erase(cur.priority);
			}
		} else {
			q.push(cur);
		}
	}
 
	// Should not happen
	return -1;
}

• 다만 pq를 사용해서 푸는건 가능할지도 모르지만 복잡할거다.
  • 왜냐면 우선순위가 높은 프로세스가 있으면 현재 프로세스를 큐에 다시 집어넣기 때문
  • 그래서 단순히 우선순위-idx 순서로 정렬하는 pq를 사용해서 돌리면 우선순위가 같을 때 idx가 작은 애가 무조건 먼저 실행되기 때문에 이런 다시 큐에 집어넣어서 발생하는 순서의 밀림을 반영할 수 없다.