[프로그래머스/c++] 프린터

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

코딩테스트 연습 - 프린터

 

---

이래저래.. 정신없어서 블로그에 글을 못 썼다!

자취방도 드디어 구하고 키키 다시 열심히 공부해야지

 

1) 풀이

우선, 가장 앞에 있는 문서를 빼고 중요도를 확인한 뒤 마지막에 넣거나 인쇄하는 과정이

필요하므로 큐(queue)를 이용해서 푸는 문제임을 알 수 있다.

priorities에 있는 문서를 큐에 모두 저장하고 빼고 넣는 과정을 진행하면 된다.

하지만 한 가지 문제가 있다.

 

대기목록에서 우리가 확인해야 할 것은 두가지이다.

1. 제일 앞 문서보다 높은 중요도의 문서가 대기목록에 남아있는가?

2. (만약, 제일 앞 문서를 인쇄한다면) 인쇄하는 문서가 요청한 문서(location)인가?

 

큐에 들어있는 문서의 중요도만 저장하고 넣고 빼는 과정을 진행하면,

중요도가 같은 문서가 있을시, 우리가 요청한 문서인지 아닌지를 파악할 수 없다!

그래서 나는 pair<int,int> 형태의 큐를 생성해주고, first에는 인덱스 즉 지금의 위치이고

second에는 문서의 중요도를 저장했다.

이렇게 저장하면 중요도와 location 모두 확인할 수 있다!

pair에 관한 설명은 3) 참고자료에!

 

그 다음, 중요도를 일일이 확인하는 작업이 필요한데,

나는 이것은 sort 함수와 스택(stack)으로 처리하였다.

 

priorities를 sort로 정렬해준 뒤 첫요소부터 끝까지 스택에 넣어주면

자연스럽게 스택의 top이 제일 큰 중요도가 오도록, 즉 top 기준으로

내림차순으로 정렬되기 때문에 스택의 top을 확인하고 현재 문서의 중요도와

같다면 스택에서 pop 해주고 아니라면 방금 큐에서 pop 했던 것을 다시 큐에 push 해주면 된다.

 

만약, 인쇄한다면 인쇄를 몇번째로 하는지 저장할 count 변수를 1 늘려주고,

지금 인쇄하는 문서가 우리가 요청한 문서라면 (first가 location과 같다면)

정답변수에 count 변수의 값을 넣어주고 확인 반복을 마친다.

 

장황하지만 스택과 큐로 쉽게 풀 수 있었던 문제!

 

2) 최종 소스코드

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <stack>
using namespace std;

int solution(vector<int> priorities, int location) {
    int answer = 0;
    queue<pair<int,int>>q; //순서와 중요도를 저장할 큐
    for(int i=0;i<priorities.size();i++){
        q.push({i,priorities[i]}); //{인덱스, 중요도}
    }
    sort(priorities.begin(),priorities.end()); //이미 priorities의 요소들을 큐에 다 집어넣었기 때문에 sort해도 괜찮음
    stack<int>s; //중요도 저장할 스택
     for(int i:priorities){
        s.push(i); 
    }
    int count=0; //인쇄하는 순서
    while(true){
        pair<int,int> cur=q.front(); //맨 앞 문서 
        q.pop();
        if(cur.second!=s.top()) q.push(cur);
        else {
            s.pop();
            count++;
             if(cur.first==location){
            answer=count;
            break;
        }
        }
    }
    return answer;
}

3) 참고자료

https://blockdmask.tistory.com/64