[C++] 백준 1966번 - 프린터 큐

---

0. 문제

 

https://www.acmicpc.net/problem/1966

1. 아이디어

 

1) '큐'만 사용해서 구현하기로 한다!!

 

2) 각각의 문서가 이미 인쇄가 되었는지를 기록해둘 bool 배열을 만들어둔다.

 

3) 중요도별 문서의 개수를 저장할 배열을 따로 생성한다! ex) 중요도가 1인 문서가 2개면 CntPerImportance[1] = 2

 

2. 소스코드

 

#include <iostream>
#include <memory.h>
#include <queue>
 
int main()
{
    int T;
    std::cin >> T;
    for (int i = 0; i < T; i++) // 테스트케이스
    {
        int N, M, index = 0, result = 1;
        bool finish = false;
        int CntPerImportance[10]; // 중요도별 문서의 개수를 저장 ex) 중요도가 1인 문서가 2개면 CntPerImportance[1] = 2
        memset(CntPerImportance, 0, sizeof(CntPerImportance));
        std::cin >> N >> M;
        bool* Importance = new bool[N]; // 문서별 인쇄여부를 저장
        for (int j = 0; j < N; j++) Importance[j] = false;
        std::queue<int> que; // 중요도가 입력된 큐
 
        for (int j = 0; j < N; j++)
        {
            int input;
            std::cin >> input;
            que.push(input);
            CntPerImportance[input]++; // 중요도별 개수 카운트
        } // 큐에 중요도 입력
        
        for (int num = 9; num >= 1; num--) // 중요도가 높은것부터 낮은순으로
        {
            
            while (CntPerImportance[num])
            {
                if (que.front() == num) // 중요도가 일치할 경우
                {
                    if (index == M) // 찾던 결과!
                    {
                        std::cout << result <<'\n';
                        finish = true;
                        break;
                    }
                    else
                    {
                        result++;
                        Importance[index] = true;
                        index = (index + 1) % N;
                        while (Importance[index])
                            index = (index + 1) % N;
                        que.pop();
                        CntPerImportance[num]--;
                    }
                }
                else // 중요도가 불일치할 경우
                {
                    index = (index + 1) % N; // 인덱스를 다음으로 설정
                    while (Importance[index])
                        index = (index + 1) % N; //만약 인덱스가 이미 인쇄된 문서라면 그 다음 인덱스로! (반복)
                    que.push(que.front());
                    que.pop();
                }
            }
            if (finish) break;
        }
        delete[] Importance;
    }
}

 

3. 결과

 

4. 피드백

 

• memset함수를 사용할 때 string.h나 memory.h를 include해주자,,
• 인덱스를 다룰 때 잘 확인하자!

---