백준 24511 queuestack

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

24511번: queuestack

입출력의 예를 살펴 보면 동작은 다음과 같다.

0 -> 큐

1 -> 스택

따라서 0 1 1 0 을 입력 받아 다음과 같은 자료형이 된다.

1(큐)

2(스택)

3(스택)

4(큐) 

형태의 자료형이 된다.

다음으로 1 2 3 4 가 입력 되면 각 자료형에 다음과 같이 자료가 추가 된다.

1(큐) -  1

2(스택)    - 2

3(스택)    - 3

4(큐) - 4

다음으로 2 가 들어 왔을 때 다음과 같이 처리가 된다.

1(큐) -  1 , 2를 push 후 1을 pop 해서 2번 자료형에 입력

2(스택)    - 2 , 1을 push 후 1을 pop해서 3번 자료형에 입력

3(스택)    - 3 , 1을 push 후 1을 pop 해서 4번 자료형에 입력

4(큐) - 4 , 1을 push 후 4를 pop해서 출력

 

다음으로 4가 들어 왔을 때 다음과 같이 처리가 된다.

1(큐) -  2, 4를 push 후 2을 pop 해서 2번 자료형에 입력

2(스택)    - 2 , 2을 push 후 2을 pop해서 3번 자료형에 입력

3(스택)    - 3 , 2을 push 후 2를 pop 해서 4번 자료형에 입력

4(큐) - 1, 2을 push 후 1를 pop해서 출력

 

다음으로 7가 들어 왔을 때 다음과 같이 처리가 된다.

1(큐) -  4, 7를 push 후 4을 pop 해서 2번 자료형에 입력

2(스택)    - 2 , 4을 push 후 4을 pop해서 3번 자료형에 입력

3(스택)    - 3 , 4을 push 후 4를 pop 해서 4번 자료형에 입력

4(큐) - 2,4을 push 후 2를 pop해서 출력

 

각 자리에는 하나만 남기 때문에 stack 인 경우에는 처음에 있는 값이 변하지 않고 큐인 경우에만 변경이 된다는 특징이 있다.

 

따라서 스택은 생각하지 않고 큐인 경우만 생각해 주면 된다.

#include <bits/stdc++.h>

using namespace std;

int type[100010];

int main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int n;
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> type[i];
    }
    deque <int> dq;
    int val;
    for(int i=1;i<=n;i++){
        cin >> val;
        if(type[i]==0) dq.push_back(val);
    }
    int m;
    cin >> m;
    for(int i=1;i<=m;i++){
        cin >> val;
        dq.push_front(val);
        cout << dq.back() << " ";
        dq.pop_back();
    }
    return 0;
}