[백준, 큐스텍] 24511 queuestack C++

---

지문 파악

0번 자료구조이면 원소를 큐에 push() 후 pop()한다.

1번 자료구조이면 원소를 스택에 push() 후 pop()한다.

 

큐인지 스택인지 말하는 배열이 N개만큼 주어진다. 즉 큐 또는 스택을 원소로하는 배열이 N개 만큼 있다고 생각하면 된다.

백준 지문 일부

N- 1번째 원소를 N -1번 자료구조(큐 또는 스택)에 push() 후 pop() 한다.

이 때 스택의 특성에 대해 살펴보자, push를() 후 pop()을 하면 넣은 원소를 다시 뺴내게 된다.

 

예제 입력 2를 보자.

백준 예제 2번

아래와 같이 넣은 원소는 그대로 나오게 되어있다. 즉 스택은 연산에서 제외해도 된다는 것이다!

스택 push() -> pop() 예시

1번 예제를 살펴보자.

queuestack 예시

원소 2를 삽입

2를 넣었으면 자료구조가 Queue일 때는 먼저있던 원소가 스택으로 전달 되고 스택은 연산을 하지 않는다 생각하면 마지막 큐에 있는 원소가 나오게 된다.

즉 ! list, deque 처럼 삽입한 원소가 앞에 있고, 마지막 원소가 나오게 되는 구조이다.

다른 예시

위의 예시를 봐도, stack은 연산에서 제외하면 된다.

 

따라서 입력한 원소가 앞에 위치하고, 마지막 원소가 나오게 되는 list, deque로 해당 문제를 풀도록 접근했다.

---

풀이

자료구조가 큐인 원소만 list, deque에 담고, stack은 담지 않는다.

입력 원소가 주어지게 되면 list의 fornt()에 삽입하고, tail()의 원소를 반환한다.

만약 list의 사이즈가 0이라면 입력 원소를 그대로 반환한다.

 

---

코드

리스트를 사용한 풀이 방법

#include <list>
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int N = 0, M = 0;
    list<int> queuestack;
    cin >> N;
    vector<int> arr = vector<int>(N);   
    
    for(int i = 0; i < N; ++i)
        cin >> arr[i];
    
    int elem;
    for(int i = 0; i < N; ++i)
    {
        cin >> elem;
        if(arr[i] == 0)
            queuestack.push_back(elem);
    }
    
    cin >> M;
    vector<int> sequence = vector<int>(M);
    
    for(int i = 0; i < M; ++i)    
        cin >>sequence[i];
     
    auto front = queuestack.front();
    auto rear = queuestack.back();
    rear--;
    
    for(int i = 0; i < sequence.size(); ++i)
    {
        if(front == rear)
            cout << sequence[i] << " ";
        else
        {
            queuestack.push_front(sequence[i]);
            cout << queuestack.back()<< " ";
            queuestack.pop_back();
        }
    }
    return 0;
}

deque를 사용한 풀이 방법

//24511번: queuestack
#include <iostream>
#include <deque>

using namespace std;

deque<int> dq;
int n,m;
bool flag[100001]; //0:queue, 1:stack

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>flag[i];
    }
    for(int i=0; i<n; i++){
        int x;
        cin>>x;
        if(flag[i]==0) //queue일때만 deque에 원소 삽입
        dq.push_back(x);
    }
    cin>>m;
    for(int i=0; i<m; i++){
        int y;
        cin>>y;
        dq.push_front(y);
        cout<<dq.back()<<" ";
        dq.pop_back();
        
    }
    //전부 stack일 경우, dq에 미리 넣는 과정없이  새 dq에 push_front, pop_back과정 반복하면 됨.

}

참조 블로그 https://velog.io/@somyeong0623/%EB%B0%B1%EC%A4%80c-24511%EB%B2%88-queuestack

[백준/c++] 24511번: queuestack