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

(6/21 - O)

첫 번째 시도에는 string을 써서 priority+location 이런 식으로 priority_queue에 담아서 compare 함수도 직접 쓰고.. 별 짓을 다 해서 어찌저찌 제출은 가능하게 했는데, 결국 나머지 테스트 케이스들에서 시간 초과였다. 썼던 코드들을 초기화하고 새로운 마음으로 다시 풀어 봤더니 두 번째 시도에 해결할 수 있었다.

 

 

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

코딩테스트 연습 - 프린터

 

 

구현

priority를 가진 문서들을 첫 번째부터 차례대로 인쇄를 시도한다. front에 있는 문서의 priority가 뒤의 문서들의 priority보다 낮다면, 이 문서는 뒤로 push된다. 이때 내가 지정한 location에 있는 문서가 몇 번째로 인쇄되는지 구한다.

 

1. 기본적으로 FIFO 형태이므로 queue를 선택한다.

2. queue<pair<int, int>>에 first:priority, second:location 형태로 원소를 차례대로 넣는다. (이하 q)

3. priority_queue<int>에 priority들을 모두 넣는다. (이하 pq)

4. q를 순회하면서, q.front().first가 pq.top()과 같은지 검사한다. 같다면 문서를 출력하는 것이므로 cnt를 증가시키고, p를 pop, pq도 한 번 pop 한다. 다르다면 q.front()를 다시 push 하고 q를 pop 한다.

 

 

코드

// 프로그래머스 고득점 Kit - 프린터

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

using namespace std;

int solution(vector<int> priorities, int location) {
    int answer = 0;

    // vector[location] = priority
    // pq에 우선순위들을 쭉 넣는다.
    int size = priorities.size();
    queue<pair<int, int>> q;
    priority_queue<int> pq;
    int loc = 0;
    for (const int& i : priorities) {
        q.push({ i, loc++ });
        pq.push(i);
    }

    int cnt = 0;
    while (true) {
        int max = pq.top();

        pair<int,int> pi = q.front();
        if (pi.first == max) {
            cnt++;
            pq.pop();
            if (pi.second == location) {
                answer = cnt;
                break;
            }
        }
        else {
            q.push(pi);
        }
        q.pop();
    }

    return answer;
}

int main()
{
    vector<int> v{ 2,1,3,2 };
    solution(v, 2);
}