[C++] 프린터

Priorities 에 있는 값을 pair<int index, int priorites[index]>로 만들어서 순서대로 queue에 push한다.
[2,1,3,2] 의 경우, queue에 <0,2>,<1,1>,<2,3>,<3,2> 이 순서로 push 시킨 것이다.
이후 priorities 내림차순으로 sort 한다. [3,2,2,1] 이 되는거임. 이게 곧 우선순위를 고려한 출력 순서가 될 것이다. 큐에서 비교의 대상이 된다.
비교하기 위해서 index = 0 값을 정의해둔다. 출력 페어의 순서를 저장하기 위해 queue<pair<int,int>> result도 정의했다.

그리고 큐가 빌때까지 무한 루프를 돈다.
사이클마다 큐 내부 비교대상은 당연히 큐의 맨 앞값이다.
조건 1) 큐의 맨 앞의 우선순위 < priorities[index]
이 경우, 우선순위가 밀리는 것이기 때문에, 큐에 프론트 값을 푸쉬하고 큐를 팝한다.
조건 2) 큐의 맨 앞의 우선순위 == priorites[index]
출력 대상이다. Answer vector에 큐의 맨 앞 값을 push_back하고 큐를 팝한다.
Index값은 1 추가한다.

이 루프가 끝나면 큐가 비었다는 뜻으로, 인쇄 순서에 맞춰서 모든 인쇄 대기 문서가 answer vector에 들어갔다는 뜻이다.
Answer의 사이즈만큼 루프를 돌면서 i 값과 answer[i].front가 같다면 i+1를 바로 return하면서 끝난다.

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

#include <algorithm>
#include <iostream>

using namespace std;


int solution(vector<int> priorities, int location) {
    int answer = 0;
    int max_index = 0;
    vector<pair<int,int>> result;
    queue<pair<int,int>> printer;
    
    for(int i = 0; i < priorities.size(); i++) {
        printer.push(make_pair(i,priorities[i]));
        // <0,2>,<1,1>,<2,3>,<3,2> index : priority pair queue
    }
    
    sort(priorities.begin(),priorities.end(),greater<>());  
    
    while(!printer.empty()) {
        if(printer.front().second < priorities[max_index]) {   //max is existed behind
            printer.push(printer.front());
            printer.pop();
        }
        else if(printer.front().second == priorities[max_index]) {  //can print
            result.push_back(printer.front());
            printer.pop();
            max_index++;
        }
    }    
    for(int i = 0; i < result.size(); i++) {
        if(result[i].first == location) {
            return i+1;
        }
    }
}

다른 사람의 풀이

기본적으로 프린터는 큐를 사용한게 같은데, 굳이 페어를 사용하지 않아도 인덱스 값을 저장하고, priorities[인덱스]로 맥스값과 비교할 수 있다.
맥스값과 같을 경우 해당 인덱스의 priorities value 를 0으로 만들어서 max_element에 걸리지 않도록 하면 된다.
문제 하나 더 풀기에 시간이 애매해서 이렇게도 짜봤다.

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

#include <iostream>
using namespace std;

int solution(vector<int> priorities, int location) {
    int answer = 0;
    queue<int> printer_q;
    vector<int> index_v;
    for(int i = 0; i < priorities.size(); i++)
        printer_q.push(i);
    
    while(!printer_q.empty()) {
        int index = printer_q.front();
        printer_q.pop();
        if(priorities[index] < *max_element(priorities.begin(),priorities.end())) {
            printer_q.push(index);
        }
        else {
            index_v.push_back(index);
            priorities[index] = 0;
        }
    }
    answer = find(index_v.begin(),index_v.end(),location) - index_v.begin() + 1;
    return answer;
}

왜인지 모르겠는데, 아래꺼가 더 느리네 흠? 왜징