[알고리즘] 프로그래머스_프린터

1. 문제 분석

• 단순히 큐에서 하나씩 뒤로 이동시키거나, 빼면 될 것 같다.
• 최대값이 작으니 효율적으로 처리하려면 priority를 나눠서 큐를 써서 각 priority의 개수로만 처리할 수 있지 않을까?

2. 문제 풀이 과정(삽질)

• 각 priority별로 나눠서 개수를 셌다.
• 내가 참고한 규칙은 낮은 priority의 마지막은 높은 priority의 전에 오거나 전에 없으면 맨 끝 원소라는 것이다.
• 하니까 3개의 테스트 케이스 빼고 모두 통과했다.
• 그런데, 끝내 처리하지 못해서 다시 간단한 방식을 하기로 했다.

3. 문제 해결

• 그냥 단순하게 location에 해당하는 원소가 pop할 순서가 될 때까지 큐를 계속 돌도록 만들었다.

4. 코드

#include <string>
#include <memory.h>
#include <vector>
#include <utility>
#include <queue>

using namespace std;

int solution(vector<int> priorities, int location) {
    int answer = 0;
    int counts[10] = {0};
    queue<int> sorted;
    queue<pair<int, int>> printer;
    
    for(int i = 0; i < priorities.size(); i++)
    {
        int now = priorities[i];
        printer.push({now, i});
        counts[now]++;
    }
    
    for(int i = 9; i >= 0; i--)
    {
        int now = counts[i];
        while(now--)
            sorted.push(i);
    }
    
    pair<int, int> document;
    while(1)
    {
        document = printer.front();
        if(document.first == sorted.front())
        {
            answer++;
            if(document.second == location)
                return answer;
            printer.pop();
            sorted.pop();
        }
        else
        {
            printer.pop();
            printer.push(document);
        }
    }
    
    return answer;
}

5. 고수의 코드를 보고 배우기

• 일단 짧다.
• 코드의 큰 차이점은 나는 {값, index} pair로 처리를 했지만, 고수의 코드는 단순히 인덱스로만 처리한 것이 눈에 띈다.
• 나는 큰 값이 남아있는지 알기 위해 우선순위별로 카운트를 하고 값의 pop마다 삭제를 했지만, 고수는 max_element(iter from, iter to)를 통해 큰 값이 남아있는지 확인해주고 간단히 넘어가 주는 것이 보인다.

#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;
    }
}