(24511) queuestack

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

단계별로 풀어보기

16단계(스택, 큐, 덱 1) 11번째

 

 

 

자료 구조는 최대 10만개, 삽입할 수열의 원소도 최대 10만개이므로 그대로 구현하면 시간 초과가 난다.

스택과 큐의 특징을 생각해보자.

스택에 원소를 넣고 빼는 경우 자기 자신이 빠지게 되므로 아무런 영향을 주지 않는다.

큐에 원소를 넣고 빼는 경우 기존 원소를 밀어내고 자신이 들어가게 된다.

종합해서 생각하면, 큐스택 자료 구조는 큐인 자료구조의 원소들만 하나의 큐에 넣은 것과 같이 생각하고 문제를 풀어도 된다.

(큐만 써도 풀 수 있지만 구현 편의 상 자료 구조의 양쪽 어디서든 넣을 수 있게 하는 것이 편해 덱을 사용했다)

 

 

 

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

int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, m;
  deque<int> dq;
  
  cin >> n;
  
  vector<int> v(n);
  
  for(int i=0;i<n;i++)  cin >> v[i];
  
  for(int i=0;i<n;i++){
    int t;
    
    cin >> t;
    
    if(!v[i])  dq.push_front(t);
  }
  
  cin >> m;
  
  for(int i=0;i<m;i++){
    int t;
    
    cin >> t;
    
    dq.push_back(t);
    
    cout << dq.front() << " ";
    
    dq.pop_front();
  }
  
  return 0;
}