프로그래머스 42587 - 프린터 (c++)

프로그래머스 42587 - 프린터

문제 링크

생각과 접근

사족

• 문제 이해를 잘 해야 삽질하지 않는다는 교훈을 얻은 문제.

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

• 처음 잘못 이해했을 때 2번 조건에서 J보다 중요도가 높은 문서가 존재하면, 그 문서를 인쇄하는 것으로 이해해서 삽질을 했다.

본론

• queue< pair<int, int> > q;
  • 큐를 사용해서 문제를 풀었다.
  • 큐를 pair를 이용해서 왼쪽에는 index, 오른쪽에는 priorities[index]를 저장하였다.
• 무한루프
  • J에 해당하는 것 q.front() 을 pop한다. (편의상 J라고 부르겠음.)
  • J를 제외한 큐를 순회해서 J의 우선순위보다 높은 원소를 찾는다.
    • 우선순위가 높은 원소가 없다면, J를 인쇄해야 한다.
      • 문제의 답은 location에 해당하는 문서의 인쇄 순서를 찾는 것이므로, J의 인덱스와 location이 일치하는지 확인한다.
        • 일치한다면, 답을 찾은 것이므로 return answer;
        • 일치하지 않는다면, 아무것도 하지 않는다. (이미 J는 pop 되었기 때문에 추가적인 작업이 필요하지 않는다.)
    • 우선순위가 높은 원소가 있다면, J를 큐의 가장 마지막에 넣어야 한다.
      • 우선순위가 높은 원소가 있다는 것을 flag에 저장하였음
      • 큐 순회가 끝나고 나면 J를 push한다.

코드

#include <bits/stdc++.h>
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(make_pair(i, priorities[i]));
    }

    while(-1){
        bool flag = true;
        int idx = q.front().first;
        int pri = q.front().second;
        q.pop();

        int size = q.size();
        for(int i = 0; i < size; i++){
            int _idx = q.front().first;
            int _pri = q.front().second;
            q.pop();

            if(pri < _pri){
                flag = false;
            }
            q.push(make_pair(_idx, _pri));
        }

        if(flag == false){
            q.push(make_pair(idx, pri));
        }
        else{
            answer++;
            if(idx == location){
                return answer;
            }
        }
    }
}

채점 결과