[BOJ 29338 // C++] Склад Оби-Вана Кеноби

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 29338번 문제인 Склад Оби-Вана Кеноби이다.
문제는 아래 링크를 확인하자.

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

 

앞 절반의 원소를 들고 있는 덱과 뒤 절반의 원소를 들고 있는 덱을 관리하자.

 

자료를 이렇게 관리하면 주어지는 모든 쿼리를 \(O(1)\)에 어렵지 않게 처리할 수 있게 되므로 문제를 간단히 해결할 수 있다.

 

아래는 제출한 소스코드이다.

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

int Q;
deque<int> L, R;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> Q;
    while (Q--) {
        string s; cin >> s;
        if (s.front() == 'a') {
            int x; cin >> x;
            R.push_back(x);
        }
        else if (s.front() == 't') {
            if (!R.empty()) R.pop_back();
        }
        else swap(L, R);
        while (L.size() > R.size()) R.push_front(L.back()), L.pop_back();
        while (L.size() + 1 < R.size()) L.push_back(R.front()), R.pop_front();
    }

    cout << L.size() + R.size() << '\n';
    for (auto &x:L) cout << x << ' ';
    for (auto &x:R) cout << x << ' ';
}