priorities location return
[2, 1, 3, 2] 2 1
으로 주어질 때
우선순위가 큰 프로세스 먼저 실행이 된다.
즉, 예제로 보면 우선순위가 3인 2번 프로세스가 먼저 실행된다.
맨 앞 부터 0번 프로세스이다.
location이 2로 주어졌으므로 2번 프로세스가 몇번째에 실행되는지 리턴하면 된다.
우선순위가 2로 동일한 프로세스(0번과 3번)가 있는데
이럴때는 앞에있는 프로세스가 먼저 실행된다고 생각하면 된다.
실행순서를 나타내자면,
1.우선순위가 2인 0번 프로세스는 우선순위가 제일 높지않다. 그러므로 맨 뒤로 넘어간다.
[1,3,2(3번프로세스),2(0번프로세스)]
2.우선순위가 1인 1번 프로세서는 우선순위가 제일 높지 않다.
그러므로 맨 뒤로 넘어간다.
[3,2,2,1]
3.우선순위가 3인 2번 프로세서는 우선순위가 제일 높다.
그렇다면 예제에서 주어진 location에 해당하는 프로세서 인지 확인한다.
맞으므로 프로세스를 실행할 수 있다.
제일 먼저 실행된 프로세스이기에 1을 return 하고 종료한다.
문제 해결 방법
그냥 queue와 priority_queue를 사용하였다.
priority_queue에는 예제에서 제시한 우선순위를 넣어서 자동으로 제일 높은 우선순위부터 정렬되게 해주었다.
queue에는 pair쌍으로 ({프로세스번호,해당 프로세스의 우선순위})로 넣어주었다.
<우선순위가 제일 높고 queue앞에 있을 경우>
qeueu의 front의 second값고 priority_queue의 front값이 동일하면(==queue앞에 있는 프로세스가 우선순위가 제일 높다는 의미) location과 queuee의 front의 first값을 비교한다.
동일하지 않다면 queue와 priority를 pop해주고 프로세스가 실행되는 횟수를 세기 위한 cnt변수를 ++해준다.
<우선순위가 높지 않고 queue앞에 있을 경우>
qeueu의 front의 second값고 priority_queue의 front값이 동일하지 않다면 queue의 맨 앞에 값만 뒤로 옮겨주면된다.
코드를 보면 이해가 더 쉽다.
#include <string>
#include <vector>
#include<queue>
using namespace std;
priority_queue<int> pq;
queue<pair<int,int>> q;
int solution(vector<int> priorities, int location) {
int answer = 0;
for(int i=0;i<priorities.size();i++){
q.push({i,priorities[i]});
pq.push(priorities[i]);
}
q={0,2}{1,1}{2,3}{3,2} 순서로 입력
pq=3,2,2,1 순서로 자동 정렬됨
int cnt=1;
while(1){
pair<int,int> qfront= q.front();
q.pop();
if(qfront.second==pq.top()){
/*queue 제일 앞에 있는 프로세스의 우선순위가 제일 높은 경우*/
if(qfront.first==location){
/*찾고자하는 프로세스 번호가 맞는 경우*/
answer=cnt;
break;
}
else{
/*우선순위는 제일 높아서 실행이 되나 location과 다른 경우
실행되므로 그냥 pop해주고
cnt++해주어서
프로세스가 몇 번째에 실행되는지 세는 cnt변수를 증가해준다.*/
pq.pop();
cnt++;
}
}
else if(qfront.second!=pq.top()){
/*프로세스가 실행되지 못한다면
queue 뒤에 다시 넣어준다.
*/
q.push({qfront.first,qfront.second});
}
}
return answer;
}