[BOJ] 1966번 프린터 큐

문제 바로가기

접근

앞에서 빼서 뒤로 다시 삽입하는 동작을 편하게 처리하려 deque 자료구조를 사용했다.

#include <bits/stdc++.h>
using namespace std;

bool comparator(const pair<int,int>& lhs, const pair<int,int>& rhs) {
  return lhs.first < rhs.first;
}

int main() {
  std::ios::sync_with_stdio(false);
  int T, N, M;
  int cnt;
  int priority, p, idx;
  deque<pair<int,int> > dq;

  cin >> T;

  for(int i = 0; i < T; i++) {
    cin >> N >> M;
    cnt = 1;

    for(int j = 0; j < N; j++) {
      cin >> priority;
      dq.push_back(make_pair(priority, j));
    }
    
    while(!dq.empty()) {
      p = dq.front().first;
      idx = dq.front().second;
      dq.pop_front();

      if(p >= max_element(dq.begin(), dq.end(), comparator)->first) {
        if(idx == M) {
          break;
        }
        else {
          cnt++;
          continue;
        }
      }
      dq.push_back(make_pair(p, idx));
    }

    dq.clear();
    cout << cnt << endl;
  }
}