개요
- 문제 설명
운영체제의 역할 중 하나는 컴퓨터 시스템의 자원을 효율적으로 관리하는 것입니다. 이 문제에서는 운영체제가 다음 규칙에 따라 프로세스를 관리할 경우 특정 프로세스가 몇 번째로 실행되는지 알아내면 됩니다.
-
실행 대기 큐(Queue)에서 대기중인 프로세스 하나를 꺼냅니다.
-
큐에 대기중인 프로세스 중 우선순위가 더 높은 프로세스가 있다면 방금 꺼낸 프로세스를 다시 큐에 넣습니다.
-
만약 그런 프로세스가 없다면 방금 꺼낸 프로세스를 실행합니다.
3.1 한 번 실행한 프로세스는 다시 큐에 넣지 않고 그대로 종료됩니다.
예를 들어 프로세스 4개 [A, B, C, D]가 순서대로 실행 대기 큐에 들어있고, 우선순위가 [2, 1, 3, 2]라면 [C, D, A, B] 순으로 실행하게 됩니다.현재 실행 대기 큐(Queue)에 있는 프로세스의 중요도가 순서대로 담긴 배열 priorities와, 몇 번째로 실행되는지 알고싶은 프로세스의 위치를 알려주는 location이 매개변수로 주어질 때, 해당 프로세스가 몇 번째로 실행되는지 return 하도록 solution 함수를 작성해주세요.
접근 방식
첫번째 시도
- 처음엔 그냥 단순히 priority_Queue에 pair형태로 {우선순위,인덱스}
이렇게 다 때려넣고 location에 해당하는 인덱스값이 top에 올때까지 pop해주고 answer값 증가시켰다.
-> 이렇게 하면 key값이 같을 때, value의 순서가 넣어준 순서와 같다고 보장을 못하므로 답이 다르게 나온다.
두번째 시도
-
따라서 새로운 방식을 찾아야했다.
0부터 9까지의 정보를 가지며 내림차순 정렬인 map과
{우선순위, 인덱스}형태의 pair<int,int>를 자료형으로 가지는 queue를 선언했다.map<int, int, greater<int>> m; //first는 우선순위, second는 원래 인덱스 queue<pair<int, int>> q; -
priorities벡터를 순회하며 해당 우선순위에 해당하는 map을 증가시키고,
queue에 {우선순위, 현재 인덱스}값을 푸시해줬다.for (int i = 0; i < priorities.size(); i++) { m[priorities[i]]++; q.push({ priorities[i],i }); } -
큐가 비어있지 않을 때까지, 반복을 한다.
각 반복에선 현재 큐의 front()가 제일 높은 우선순위가 아닐 시,
큐의 front()값을 뒤로 push()한다.while (!q.empty()) { //제일큰 우선순위보다 현재 우선순위가 작으면 뒤로 if (q.front().first < (*m.begin()).first) { q.push(q.front()); q.pop(); }현재 큐의 front값이 제일 큰 우선순위라면 먼저 index값이 location인지 검사 후,
//제일큰 우선순위면 해당 우선순위 갯수 제거하고 map에서도 해당 우선순위 제거 else if (q.front().first == (*m.begin()).first) { if (q.front().second == location) { break; }location이 아니라면 answer을 증가시키고, front값을 pop해준다.
그 후, 해당 우선순위의 갯수정보를 가진 map에서
우선순위의 갯수가 1보다 클때는 1감소시키고, 아니면 해당 우선순위를 제거해준다.answer++; if ((*m.begin()).second > 1) (*m.begin()).second--; else m.erase(m.begin());
전체 코드
#include <string>
#include <vector>
#include <map>
#include<queue>
#include<iostream>
using namespace std;
int solution(vector<int> priorities, int location) {
int answer = 1;
//key에 해당하는 우선순위가 몇개인지 저장하는 map
map<int, int, greater<int>> m;
//first는 우선순위, second는 원래 인덱스
queue<pair<int, int>> q;
for (int i = 0; i < priorities.size(); i++) {
m[priorities[i]]++;
q.push({ priorities[i],i });
}
while (!q.empty()) {
//제일큰 우선순위보다 현재 우선순위가 작으면 뒤로
if (q.front().first < (*m.begin()).first) {
q.push(q.front());
q.pop();
}
//제일큰 우선순위면 해당 우선순위 갯수 제거하고 map에서도 해당 우선순위 제거
else if (q.front().first == (*m.begin()).first) {
//location인덱스라면 탈출
if (q.front().second == location) {
break;
}
//아니면 제거후, 우선순위의 갯수정보 업데이트
q.pop();
answer++;
if ((*m.begin()).second > 1) (*m.begin()).second--;
else m.erase(m.begin());
}
}
return answer;
}문풀후생
사실 priority_Queue와 queue를 동시에 사용하면 위 구현을 좀 더 간단히 풀 수 있다.
priority_queue를 사용한 코드
#include <string>
#include <vector>
#include <map>
#include<queue>
#include<iostream>
using namespace std;
//정렬을 할 이유가 없음
int solution(vector<int> priorities, int location) {
int answer = 1;
priority_queue<int, vector<int>, less<int>> pq;
//first는 우선순위, second는 원래 인덱스
queue<pair<int, int>> q;
for (int i = 0; i < priorities.size(); i++) {
pq.push(priorities[i]);
q.push({ priorities[i],i });
}
while (!q.empty()) {
//제일큰 우선순위보다 현재 우선순위가 작으면 뒤로
if (q.front().first < pq.top()) {
q.push(q.front());
q.pop();
}
//제일큰 우선순위면 해당 우선순위 갯수 제거하고 map에서도 해당 우선순위 제거
else if (q.front().first == pq.top()) {
//location인덱스라면 탈출
if (q.front().second == location) {
break;
}
//아니면 제거후, 우선순위의 갯수정보 업데이트
pq.pop();
q.pop();
answer++;
}
}
return answer;
}pq에는 우선순위값만들어가면 되므로 인자가 pair형이 아니라 int형이다.
