백준 문제 24511번 queuestack c++

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

24511번: queuestack

 

문제해석

 

이걸 그냥 문제설명처럼 구현하면 100000*100000만큼 걸려서 시간초과난다.

스택의 특성상 맨 처음의 있던값은 절대 pop되지않는다.

따라서 큐만 살펴보면되는데 예시의 입력을 그림으로 살펴보자.

 

아래 부분이 front이다.

초기 상태엔 각 자료구조에 1 2 3 4가 들어있다.

2를 넣고난 후의 상태이다.

마지막에 4가 빠져나온것을 초록색으로 써놨는데 최종 초록색이 답이 된다.

4를 넣고난 후의 상태이다.

 

 

7을 넣고난 후의 상태이다.

 

 

따라서 답은 4 1 2가 된다.

 

그림상에서 확인 할 수 있듯이 스택자료구조는 있으나 마나이고 큐만 보면된다.

여러 큐를 하나로 볼수있는데 맨 마지막 큐의 초기값이 front에 위치시킨 하나의 큐로 볼수가 있다.

즉 아래 그림처럼 초기 값이 세팅 되어있다고 생각하면 된다.

 

그리고 큐에 하나를 푸쉬할때마다 큐의 맨 앞 원소를 팝 해주면 최종적으로 아래 그림처럼 나온다.

 

 

#include <iostream>
#include <queue>
#include <stack>
using namespace std;
stack <int> st;
queue <int> q;
bool flag[100000];
int main(){
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    int n,m,input,x;
    cin>>n;
    for(int i=0; i<n; i++)
    {
        cin>>flag[i];
    }
    for(int i=0; i<n; i++)
    {
        cin>>input;
        if(flag[i]==0)
        {
            st.push(input);
        }
    }
    while(!st.empty())
    {
        q.push(st.top());
        st.pop();
    }
    cin>>m;
    for(int i=0; i<m; i++)
    {
        cin>>input;
        q.push(input);
    }
    for(int i=0; i<m; i++)
    {
        cout<<q.front()<<" ";
        q.pop();
    }
}