[C++] 백준 24511 queuestack

1. 문제

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

 

2. 문제 이해

이 문제를 처음 읽으면 "이게 뭐야"라는 말이 절로 나온다.

문제 이해만 한다면 정말 쉬운 문제이니 문제 이해부터 진행해 보겠다.

 

앞부분 입력

 

각 자료구조(0 : queue, 1 : stack)에 값을 하나씩 넣어두는 과정이라고 생각하면 된다.

이렇게 개별적인 큐와 스택을 모아둔 전체를 이 문제에서는 queuestack이라고 한다.

 

뒷부분 입력

위에서 만든 queuestack에 첫 부분(스택 or 큐)에 push 시킬 값을 입력받는다.

• queuestack에 push를 시키고 pop을 바로 시킨다.
  • 스택이면 push 한 값이 바로 pop
  • 큐라면 기존에 들어있던 값이 pop

• 이렇게 pop 된 값이 다음 부분(스택 or 큐)에 push 된다.

 

위 과정이 반복되고 마지막 부분에 pop 된 값이 바로 결괏값이다.

입력에 따른 이 마지막 return값을 구하는 것이 문제의 답.

 

백준 첫 번째 예시) queuestack에 2를 넣었을 때의 리턴값

 

3. 풀이과정

스택에 push 되는 값과 pop 되는 값은 동일하다. 따라서 queue 스택에서 stack은 없다고 쳐도 된다.

따라서

위 입력으로 만든 queuestack을 아래로만 생각할 수 있다.

0   0

1    4

💡 따라서 덱에 push_front를 시키고, 그때 pop 시킨 값이 바로 queuestack의 리턴값이다.

 

4. 📄전체 코드

#include <iostream>
#include <deque>
#include <vector>
using namespace std;

int main()
{
    ios::sync_with_stdio(false); cin.tie(NULL);
    int n;
    cin >> n;
    vector <int> dataStructure(n); //스텍인지 큐인지 입력받기
    for (auto& i : dataStructure){
        cin >> i;
    }

    deque <int> queuestack;
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        //큐인 경우에만 처리, 스택은 없다고 침(push값 = pop값) 
        if (dataStructure.at(i) == 0) 
            queuestack.push_back(x);
    }
    int m;
    cin >> m;
    for (int i = 0; i < m; i++)
    {
        int x;
        cin >> x;
        queuestack.push_front(x);
        cout << queuestack.back() << " ";
        queuestack.pop_back();
    }
    return 0;
}