프로그래머스 - 프린터 c++

이전에 백준에서 비슷한 걸 풀어봤어서 어렵지 않게 풀었다. 

이게 제일 효율적이진 않더라도 내가 전에 짰던 거보다 잘 짠 듯

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

using namespace std;
bool compare(int a, int b){
    return a > b;
}

int solution(vector<int> priorities, int location) {
    int answer = priorities.size();
    //vector<pair<int,int>> max_idx;
    //큐에 집어 넣어준다. //자신의 중요도 및 원래 인덱스 
    queue<pair<int,int>>q;
    for (int i=0; i<priorities.size();i++){
        q.push({priorities[i],i});    
    }
    //중요도가 큰 순으로 내림차순으로 정리됨 
    sort(priorities.begin() , priorities.end() , compare);

    int idx = 0;
    while(!q.empty()){
        if (q.front().first == priorities[idx] && q.front().second == location){
            return answer = idx+1;
        }
        else if (q.front().first == priorities[idx] && q.front().second != location){
            q.pop();
            idx++;
        }
        else {
            int first_num = q.front().first;
            int second_num = q.front().second;
            q.pop();
            q.push({first_num , second_num});
        }
    }
    return answer;
}

중요도와 자신의 고유 인덱스를 담는 큐를 만들었다. 

그 후 중요도들을 sort해 가장 내림차순으로 만들어주었다.  그때 그 순간의 가장 큰 중요도가 무엇인지 알기 위해서 

 

1. 만약 큐의 front가 현재 가장 큰 중요도가 아니라면 pop 해준 후 그대로 다시 넣어준다.

 

2. 큐의 front가 현재 가장 큰 중요도지만 내가 찾는 고유 인덱스는 아니라면 ? 

큐를 뺴주기만 하고 중요도 인덱스를 하나 더 추가 시켜준다. 그래야 그 다음의 새로운 중요도가 업데이트 된다. 

 

3. 큐의 front가 현재 가장 큰 중요도이면서 내가 찾던 인덱스라면 ? 

잘 생각해보면 출력이 될 떄 즉 2번과 같은 상황마다 idx가 하나씩 늘어난다 => 즉 출력횟수 -1 과 같다.

 

 

 

다른 사람들이 푼 풀이도 보자

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

using namespace std;

int solution(vector<int> priorities, int location) {
    queue<int> printer;                         //queue에 index 삽입.
    vector<int> sorted;                         //정렬된 결과 저장용
    for(int i=0; i<priorities.size(); i++) {
        printer.push(i);
    }
    while(!printer.empty()) {
        int now_index = printer.front();
        printer.pop();
        if(priorities[now_index] != *max_element(priorities.begin(),priorities.end())) {
            //아닌경우 push
            printer.push(now_index);
        } else {
            //맞는경우
            sorted.push_back(now_index);
            priorities[now_index] = 0;
        }
    }
    for(int i=0; i<sorted.size(); i++) {
        if(sorted[i] == location) return i+1;
    }
}

 이 사람들은 인덱스를 가지고 비교했다.

1. now_index 는 큐 맨 앞부분에 있는 인덱스다.

2. 이 인덱스에 해당하는 중요도가 중요도 배열의 최댓값과 다르다면  다시 넣어준다. 

3. 만약 이 인덱스에 해당하는 중요도가 중요도 배열의 최댓값과 같다면 sorted라는 새로운 벡터에 인덱스를 저장해준다. 그 후 해당 인덱스의 중요도를 0으로 만들어준다. 

 4. sorted라는 배열에는 인덱스들이 저장되어있다. 만약 그 인덱스가 내가 찾는 값과 같다면 그 인덱스가 위치한 순서 즉 출력된 순서를 반환해준다.