[Programmers] 프린터

프로그래머스 - 프린터 문제입니다.

 

문제

입출력 예

우선순위가 가장 높은 목록 부터 차례대로 꺼내야 하고 location이 자신이 요청한 문서의 위치이므로

priorities 배열에서 가장 높은 순서대로 출력해야 합니다.

priorities 를 정렬하면 index 위치가 섞이기 때문에 처음 index와 우선순위를 알고 있어야 합니다.

 

가장 초기의 인덱스와 우선순위를 함께 큐에 저장하고 우선순위 배열을 정렬합니다.

큐에서 가장 앞 데이터의 우선순위가 처음 출력되어야 하는 우선순위 보다 낮다면 큐의 가장 뒤로 보냅니다.

현재 출력되어야 하는 우선순위와 큐의 가장 앞에 있는 우선순위가 같다면 출력하고 answer를 1 더합니다.

이때 location의 인덱스와 같다면 정답이 됩니다.

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

using namespace std;

bool cmp(int a, int b) {	// 내림차순 정렬
    return a > b;
}

class Data {
    public:
    int index;
    int priority;
    
    Data() {}
    Data(int index, int priority) {
        this->index = index;
        this->priority = priority;
    }
};

int solution(vector<int> priorities, int location) {
    int answer = 0;
    int i;
    queue<Data> q;
    Data d;
    
    for(i = 0; i < priorities.size(); i++) {	// 초기 인덱스와 우선순위 함께 저장
        q.push(Data(i, priorities[i]));
    }
    
    sort(priorities.begin(), priorities.end(), cmp);	// 우선순위 배열 정렬
    
    while(!q.empty()) {
        if(priorities[answer] > q.front().priority) {	// 큐의 가장 앞 데이터의 우선순위가 현재 출력되어야 하는 우선순위보다 작다면
            d = q.front();
            q.pop();
            q.push(d);
        }
        else if(priorities[answer] == q.front().priority) {		// 큐의 가장 앞 데이터의 우선순위가 현재 출력되어야 하는 우선순위와 같다면
            answer++;	// 출력 후 다음 우선순위로 넘어감
            if(q.front().index == location) break;	// 내가 요청한 인쇄물과 위치가 같다면 정답
            q.pop();
        }
    }
    return answer;
}