[백준] 1966.cpp : 프린터 큐

www.acmicpc.net/problem/1966

1966번: 프린터 큐

#include <iostream>
#include <deque>
using namespace std;

int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int testCases = 0;
    cin >> testCases;
    for(int tc = 0 ; tc < testCases ; tc++)
    {
        int n, m;
        cin >> n >> m;
        int val = 0;
        deque<int> que;

        // 덱에 다 집어넣어준다
        for(int i = 0 ; i < n ; i++)
        {
          cin >> val;
          que.push_back(val);
        }

        int prior = m; // 내가 목표로 하는 문서의 인덱스
        int printCount = 0; // 몇번째 출력중인지 확인

        // 계속 반복하다가 출력하려는 문서가 prior 이라면 빠져나온다.
        while(1)
        {
          int i = 0;
          // 내 뒤에있는 문서들 완전탐색
          for(i = 0 ; i < que.size() ; i++)
          {
            if(que[i] > que[0]) // 만약 나보다 큰 놈이 있으면
            {
              que.push_back(que[0]); // 맨 뒤로 옮겨주고
              que.pop_front();
              if(prior == 0) prior = que.size() - 1; // 만약 목표문서를 옮긴거라면 인덱스도 맨 뒤로
              else prior--; // 목표문서가 아니라면 앞에서 하나 땡겨졌기 때문에 1 감소

              break;
            }
          }
          // 만약 중간에 빠져나온 거라면 밑을 실행하지 않음
          if(i != que.size()) continue;
          // 내 뒤에 나보다 우선순위 큰 문서가 없을 경우에
          if(prior == 0) // 이번에 뽑을 문서가 내가 목표로 하던 문서라면
          {
            printCount++; // 프린트해주고 빠져나감
            break;
          }
          else // 내가 목표로 하던 문서가 아니라면
          {
            que.pop_front(); // 프린트해주고
            printCount++;
            prior--; // 하나 빠졌으니 목표 인덱스도 1 감소
          }
        }

        cout << printCount << '\n';
    }
}

 

[Try]

1. 문제에 주어진 대로 정직하게 풀려고 했다. 대신 아무래도 원소들을 접근해야하다보니 큐가 아닌 덱 자료구조를 사용하였고, 매 번

     출력할때마다 뒤의 원소들을 다 비교해보는 방식을 택했다.

 

[Point]

1. 처음에 m 으로 준 인덱스값을 한번씩 처리할때마다 잘 컨트롤해서 위치를 바꿔주는게 중요한 것 같다. 그래야 해당 문서가 출력 되

     는 타이밍에 빠져나올 수 있다.

2. 다른 분들 코드가 왜이렇게 눈에 안들어오는거지... 사고가 너무 막혀있는 건가

3. 시뮬레이션이라고 분류가 되어 있는데, 이건 특정 패턴을 찾아서 푸는건가? (7395659 번)

 

[More]