[프로그래머스] 스택/큐 - 프린터

프로그래머스 - 프린터

문제 설명

대기목록에서 우선순위가 높은 문서부터 출력할 때, 내가 요청한 문서가 몇 번째로 인쇄되는지 return 하기

제한사항

대기목록에는 1개 이상 100개 이하의 문서가 있다.
인쇄 작업의 중요도는 1~9로 표현하고, 숫자가 클수록 중요하다.
location은 대기목록의 index를 의미한다.

문제풀이

1. 대기목록에 맨 앞에 있는 문서보다 더 중요한 문서가 뒤에 있는지 확인한다.
2. 더 중요한 문서가 뒤에 있으면 맨 앞의 문서를 맨 뒤로 보낸다.
3. 더 중요한 문서가 없으면 맨 앞의 문서를 출력한다.

코드

#include <string>
#include <vector>
#include <list>

using namespace std;

list <pair<int, int>> waiting_list;

void Make_list(vector<int> priorities){
    for(int i=0; i<priorities.size(); i++){
        waiting_list.push_back(make_pair(i,priorities[i]));
    }
}

bool Is_first(){
    int front = waiting_list.front().second;
    bool is_first = true;

    list <pair<int, int>>::iterator iter;
    for(iter=waiting_list.begin(); iter!=waiting_list.end(); iter++){
        if(front < iter->second){
            is_first = false;
            break;
        }
    }
    
    return is_first;
}

int solution(vector<int> priorities, int location) {
    int answer = 0;
    bool is_first;
    Make_list(priorities);
    
    while(1){
        is_first = Is_first();
        if(!is_first){
            pair<int, int> new_back = waiting_list.front();
            waiting_list.push_back(new_back);
        }
        else{
            answer ++;
            if(waiting_list.front().first == location) break;
        }
        waiting_list.pop_front();
    }
    
    return answer;
}

시간 복잡도

Worst case : 대기목록이 descending order 되어 있는 경우 + 맨 마지막 문서의 출력 순서를 return하는 경우
시간복잡도 : O(N^2)
N : 대기목록의 크기

스택/큐 문제에 list를 사용한 이유

처음에 큐를 사용하려고 했으나, 반복문으로 큐 안의 모든 원소들에게 접근해서 값을 확인해야 했다.
하지만 큐는 index를 사용해서 원소에 접근할 수 없어서 불편했다.
원소 접근이 많은 경우에는 스택/큐보다 list를 사용하면 pop, push가 자유롭고, index를 사용해서 원소에 접근할 수 있어서 더 편하다는 글을 보고 list를 사용하게 되었다.

참고 사이트

List of C++