[백준] 24511번 queuestack C++ 코드

코드

// 데이터 양이 10만이라 최대 O(NlogN)으로 해결해야함
// 스택은 아무런 영향을 끼치지 못함
#include <iostream>
#include <deque>
using namespace std;
int n, a[100002],m,nxt;
deque<int> dq;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> n;
  for(int i = 0; i < n; i++) {
    cin >> a[i];
  }
  for(int i = 0; i < n; i++) {
    int k = 0;
    cin >> k;
    if(a[i] == 0) dq.push_back(k);
  }
  cin >> m;
  for(int i = 0; i < m; i++) {
    cin >> nxt;
    dq.push_front(nxt);
    cout << dq.back() << " ";
    dq.pop_back();
  }
  return 0;
}

처음에 O(N^2)로 했다가 시간초과를 받았다. stack은 아무 영향을 끼치지 못하는 걸 알고 설계했는데 10만인 걸 못 보고 작성했더니 초래된 결과였다. O(N)으로 해결할 수 있는 문제. 효율적인 풀이를 생각하는 것이 관건인 듯하다.