[프로그래머스 코딩테스트 고득점 Kit - 스택/큐] 프린터

큐 문제

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

 

---

[문제 풀이]

 

원형으로 계속 돌아가는 문서 중 우선순위가 가장 높은 것을 먼저 출력하는 문제입니다.

원형으로 문서를 계속 돌리고 확인해야 하므로 큐를 써야 한다고 생각할 수 있습니다.

 

가장 직관적으로 생각해보면 우선 배열을 순회하면서 1~9까지의 중요도가 몇 개씩 있는지 확인하고 큐 안에 문서에 대한 정보를 넣어야 합니다.

 

구해야 하는 답이 위치를 기반으로 찾게 됩니다.

그러므로 큐 안에 넣을 문서에 대한 정보는 위치가 필수적으로 들어갑니다.

중요도까지 넣어도 되지만 위치를 넣었다면 그 위치에 대한 중요도를 priorities배열로 구할 수 있기 때문에 넣지 않아도 좋습니다.

 

예를 들어 priorities가 1 1 3 6 6 7 8 8 8 9처럼 주어졌다면

 

큐는 아래 두 표 중 하나와 같고

 

[위치만 저장한 경우] → 이 경우는 priorities배열로 중요도를 불러와야 함

0

1

2

3

4

5

6

7

8

9

[위치와 중요도를 묶어서 저장한 경우]

[0, 1]

[1, 1]

[2, 3]

[3, 6]

[4, 6]

[5, 7]

[6, 8]

[7, 8]

[8, 8]

[9, 9]

 

중요도를 기록한 배열은 아래와 같습니다.

중요도 (i)	1	2	3	4	5	6	7	8	9
개수 (arr[i])	2	0	1	0	0	2	1	3	1

 

이제 중요도 k를 9부터 1까지 확인하면서 남은 중요도의 개수 arr[k]가 0이라면 k를 낮춰가고, 그렇지 않다면 현재 중요도 k인 문서가 나올 때까지 큐의 front를 제거하고 다시 큐에 넣는 작업을 반복하여 가장 마지막으로 보내줍니다.

현재 중요도 k인 문서가 나왔다면 arr[k]를 1씩 낮추고 현재 문서를 큐에서 빼버려서 인쇄했음을 확정하면 됩니다.

 

문서를 인쇄할 때마다 count를 1씩 증가시키고 인쇄한 문서가 location에서 원하는 위치와 같았다면 반복문을 종료하고 count를 return 하면 됩니다.

그러므로 count를 저장할 변수를 한 개 만들어 줍시다.

 

모든 문서에 대해 큐를 돌리는 것이 비효율적일 수 있으므로 시간 복잡도를 구해봅시다.

문서를 한 바퀴 돌리면서 현재 중요도의 문서를 빼내는 작업을 진행합니다.

즉 모든 중요도 p에 대해 N개 이하의 문서를 한 바퀴 돌리면서 확인하므로 $O(Np)$의 시간 복잡도를 갖는다는 것을 알 수 있습니다.

 

대기 목록 N이 100 이하이고 중요도 p가 9 이하이므로 해당 풀이로도 빠른 시간 안에 구할 수 있습니다.

문제가 큐를 사용하는 문제라는 것을 납득하기 쉬워서 나름 간단한 문제였습니다.

 

---

[소스 코드] / C++

 

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

using namespace std;

int solution(vector<int> priorities, int location) {
    int answer = 0, N = priorities.size();
    
    int countPrior[10] = {0, };
    queue<pair<int, int>> q;
    
    for (int i = 0; i < N; i++) {
        int p = priorities[i];
        q.push(make_pair(i, p));
        ++countPrior[p];
    }
    
    for (int p = 9; p > 0; ) {
        if (countPrior[p] == 0) {
            --p;
            continue;
        }
        
        pair<int, int> cur = q.front();
        q.pop();
        
        if (cur.second == p) {
            ++answer;
            --countPrior[p];
            if (cur.first == location) break;
        } else q.push(cur);
    }
    
    return answer;
}

 

---

[메모]

 

• c++의 배열을 초기화할 때는 fill, fill_n을 사용하는 것이 좋다. memset이 가능하다면 memset의 퍼포먼스를, 불가능하다면 iterator로 초기화를 해주는 함수
• fill(iter, iter, val), fill_n(iter, len, val)
• c++에서 배열의 값을 일부만 지정해주어도 나머지는 0으로 초기화가 된다. 위의 int arr[10] = {0, }과 같은 방법

좋은 자료

www.soen.kr/lecture/ccpp/cpp4/42-2-2.htm