[BOJ알고리즘, C++]#24511_queuestack, 덱

 

[BOJ알고리즘, C++]#24511_queuestack

 

BOJ 알고리즘 문제 풀이, 24511번 문제 queuestack

덱을 활용하여 푸는 문제

 

---

 

Overview

 

1. 문제
2. 풀이
3. 코드

 

#1. 문제

 

 

#2. 풀이

1. 덱

[자료 구조]#0_선형 자료구조

 

[Basic C++] #68_deque

 

Details

 

• 덱은 스택과 큐의 특성을 모두 가지고 있는 선형 자료구조로, 목록의 각 양쪽 끝에서 삽입과 제거 연산을 모두 수행할 수 있습니다.

 

2. 스택 + 큐 = 덱

1. 문제를 해결하기 위해 말 그대로 큐와 스택의 특성을 모두 갖고 있는 덱 자료구조를 활용합니다.
2. 먼저, Ai = 0 은 큐를 의미하며, Ai = 1 은 스택을 의미합니다. 문제가 제시한 조건에 따르면, 큐는 선입선출 방식으로 동작하는 선형 자료구조로 새롭게 삽입한 데이터가 기존의 데이터를 밀어내고 자리를 차지합니다. 반대로, 스택은 후입선출 방식으로 동작하는 선형 자료구조로 새롭게 삽입한 데이터가 다시 제거됩니다. 최종적으로, Ai = 0, 즉 큐일 경우만 해당 위치의 원소가 새로운 원소로 바뀌며, Ai = 1, 스택일 경우 원소가 바뀌지 않습니다.
3. 따라서, 주어진 배열에서 "큐" 자료구조를 가지는 위치만 고려합니다.

 

#3. 코드

 

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

bool arr[100001];

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    
    int N;
    deque<int> dq;
    cin >> N;
    for(int i=0; i<N; i++)
    {
        cin >> arr[i];
    }
    for(int i=0; i<N; i++)
    {
        int tmp;
        cin >> tmp;
        if(arr[i]) continue;
        dq.push_back(tmp);
    }
    
    int M;
    cin >> M;
    while(M--)
    {
        int tmp;
        cin >> tmp;
        dq.push_front(tmp);
        cout << dq.back() << ' ';
        dq.pop_back();
    }
    
    return 0;
}