알고리즘, 프로그래머스/프린터

출처

https://school.programmers.co.kr/learn/courses/30/lessons/42587

---

조건

 1. 인쇄 대기목록의 가장 앞에 있는 문서J를 대기목록에서 꺼냄.
 2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 대기목록의 가장 마지막에 넣기.
 3. 그렇지 않으면 J를 인쇄.

---

매개변수

vector<int> priorities : 인쇄 대기목록 배열
int location : 요청한 문서의 현재 대기목록의 위치

---

추천 해결 방법

• 스택/큐 사용

---

연구

#1
가장 중요시 했던 점은 대기목록에서 현재 문서보다 우선순위가 높으면 대기목록으로 돌려보낸다는 점이었다. 조건 1을 통해 큐를 사용해야한다는 것은 알았지만, 어떻게 남은 목록에서 대기 순위가 높은 것을 확인하여 돌려보낼 수 있냐는 것이었다. 큐에 대해 알아보던 중 우선 순위 큐에 대해 알게 되었다. cpp STL에서 제공하는 pirority_queue를 찾아보았지만, 같은 우선순위 내에서 순서가 바뀌지 않는 듯 보였다(정확히 읽어보면 다를 수도 있다. 우선순위 큐에 대해 이해가 부족하기 때문). 그래서 priority_queue는 쓰지 않았다.

큐를 우선 순위가 가장 높은 것을 찾기 전까지 나온 문서들을 저장하기 위한 항목으로 사용하고 큐의 top 보다 큰 우선 순위를 가진 문서가 나오면 대기열로 다시 추가하였다. 순서가 자주 변경되는 상황상 location으로 원하는 항목을 특정지을 수 없어 int* 자료형으로 대기 목록과 큐를 구성하게 되었다.

#include 
#include 
#include 

using namespace std;

int solution(vector priorities, int location) {
    int answer = 0;
    vector arr;
    for(int i = 0;i que;
    while(true){
        if(arr.empty()){
            auto data = que.front();
            que.pop();
            answer++;
            if(data == &priorities[location]) return answer;
            while(!que.empty()){
                data = que.front();
                arr.push_back(data);
                que.pop();
            }
        }
        if(!que.empty()&&(*(que.front())<*(arr[0]))){
            while(!que.empty()){
                arr.push_back(que.front());
                que.pop();
            }
        }else{
            que.push(arr[0]);
            arr.erase(arr.begin());
        }
    }
}

#2
문제를 해결하고 나니, 우선순위가 가장 큰 것을 기준으로 대기열이 앞 뒤로 나뉜다는 특징이 눈에 띄었다. 배열을 반으로 나눠서 정렬을 하는 것은 알고리즘에서 가장 쉽게 접했던 것이라 배열로 접근하여 해결해보고자 한다.