BOJ 24511 (S3) queuestack

문제 요약

크기가 1인 스택(1)과 큐(0)가 무질서하게 반복등장할 때,
주어진 수열을 자료구조에 입출력한 결과를 출력해보자.
(단, 스택과 큐의 길이는 최대 2(push), 최소 1(pop)이다.)

풀이 방향

예를 들어 1이 들어있는 크기가 1인 스택과 큐에,4를 입출력해보자.

top은 다음 자료구조로 이동할 데이터다.

stack의 경우
push(4) -> 1,4
top() == 4
pop() -> 1

queue의 경우
push(4) -> 1,4
front() == 1
pop() -> 4

결과에서 확인할 수 있듯, stack에서는 변화가 없다.
따라서 stack에 대한 모든 경우를 제외하고 queue에 대해서만 풀이를 진행하면 된다.

제출 답안

#include <iostream>
#include <queue> //queue, vector
#include <stack>
using namespace std;

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int n; cin >> n;
    vector<int> v(n);
    for(int i=0; i<n; i++)
        cin >> v[i]; //a수열 입력
    
    stack<int> st;
    for(int i=0; i<n; i++) {
        int x; cin >> x;
        if(v[i]==0) //queue일 때 b수열 입력, 나머지 stack일 때 값은 버림
            st.push(x);
    }
    
    queue<int> q;
    while(!st.empty()) {
        q.push(st.top());
        st.pop();
    }
    
    int m; cin >> m;
    vector<int> c(m);
    for(int i=0; i<m; i++) {
        cin >> c[i]; //c수열 입력
        q.push(c[i]);
        cout << q.front() << ' ';
        q.pop();
    }
    return 0;
}

답안 해설

결과적으로 문제에 등장하는 queue만으로 문제를 해결할 수 있다는 점은 알아냈지만, 출력하는 방향도 고려해봐야 한다.

queue는 선입선출(FIFO)으로,
각 큐 [1], [2], [3], [4]에 5를 차례로 입출력한다면, 마지막 큐 [4]에서 3을 입력, 4를 출력하게 된다.
단순히 하나의 큐에 1,2,3,4를 입력하고 5를 입출력하는 과정과는 차이가 있다.

나는 이 문제를 가장 쉽게 해결하기 위해서, 반대방향으로(4,3,2,1 순으로) queue에 입력하는 쪽을 선택했다.
구현은 미리 새로운 스택에 받아놓은 후 차례로 큐에 push pop하는 방식을 선택했다.

시간초과 방지를 위해 빠른입출력까지 작성해주면 큰 문제는 없다.

마지막으로 스포하자면!!
queue,stack이 모두 등장하는 자료구조여서가 아니라 각 queue를 하나의 stack처럼 쌓아놔서 queuestack이 아닌가 싶다.

이 문제와 관련된 좋은 문제
BOJ 2164 (S4) 카드2
BOJ 1966 (S3) 프린터 큐

추가로 읽어보면 좋은 내용

• cpp stl stack 라이브러리 내장함수
• cpp stl queue 라이브러리 내장함수