[프로그래머스, C++] 프린터(스택/큐 파트)

문제 링크

코딩테스트 연습 - 프린터

 

 

 

풀이

문제를 보면 Queue 문제를 느낄 수 있었다.

우선순위 큐(Priority Queue) 문제로 보았는데 같은 원소가 중복될 수 있어서 일반 Queue를 사용했다.

문제에 주어진 작업 순서대로 수행하였다.

 

// init

1. 우선순위 목록을 검색할 수 있는 v(vector) 컨테이너를 내림차순으로 정렬한다.

2. Queue에 원소들을 넣는다.

 

// process

Queue에 원소가 남아있지 않을 때까지 반복문을 돌린다

{

    제일 앞에 있는 원소를 pop()한다.

    그 원소가 우선순위 목록과 비교한다.

    그 원소가 우선순위가 작다면 push(원소)로 뒤에 넣어주고

    반대면 우선순위 목록(v)의 인덱스를 증가시킨다.

    만약, 해당 원소가 우선순위도 가장 크고 인쇄를 요청한(알아낼) 원소라면 break; 해준다.

}

 

++

우선순위 목록(v)의 인덱스가 몇 번째 출력인지와 같다(정확히는 1 차이!)

answer는 location값을 이어받아서 인쇄를 요청한 문서의 현재 인덱스를 계속 체크해준다.

 

 

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

using namespace std;

// 중요도가 높은 문서를 먼저 인쇄하는 프린터 개발
// 인쇄 대기목록의 가장 앞에 있는 문서(j)를 대기목록에서 꺼낸다
// 나머지 인쇄 대기 목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣는다.
// 그렇지 않으면 J인쇄

// 중요도 priorities
// 인덱스 location

int solution(vector<int> priorities, int location) {
    int answer = 0;
    
    // init
    vector<int> v(priorities);      // 복사 생성자
    sort(v.rbegin(), v.rend());     // 내림차순 정렬
    queue<int> q;
    for(auto e: priorities) q.push(e);
    
    // process
    int i=0;                // 몇 번째 출력인지
    answer = location;          // 요청한 문서의 인덱스
    while(!q.empty()){
        int e = q.front();
        q.pop();
        if(e < v[i]) q.push(e);     // 나보다 우선순위가 큰 것이 있다.
        else{       // 내 우선순위가 가장 크다
            i++;
            if(answer==0) break;        // 인쇄를 요청한 문서 = 현재 출력할 문서
        }
        answer--;       // 요청한 문서의 인덱스
        answer = answer < 0 ? q.size()-1 : answer;
    }
    answer = i;
    return answer;      // location이 언제 인쇄되는지 리턴
}