[BOJ알고리즘, C++]#5430_AC, 덱, 양방향 큐

 

[BOJ알고리즘, C++]#5430_AC

 

BOJ 알고리즘 문제 풀이, 5430번 문제 AC

deque 컨테이너를 활용하는 방법에 대해 알아보겠습니다.

 

---

 

Overview

 

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

 

#0. 문제

 

 

#1. 풀이

1. 양방향 큐

• 양방향 큐는 데이터 목록의 양쪽 끝에서 데이터의 삽입과 삭제가 모두 가능한 큐 자료구조의 한 종류입니다.
• 양방향 큐는 양쪽 끝에서 데이터의 삽입과 삭제가 모두 가능해 크기가 유연하며, 슬라이딩 윈도우 알고리즘 혹은 양쪽에서 접근해야 하는 큐 기반의 문제 등에 활용됩니다. 

 

2. deque 컨테이너

[Basic C++] #68_deque

 

3. deque 컨테이너의 삽입/삭제, begin()과 rbegin()

• 먼저, deque 컨테이너에 항목들을 저장합니다.
• "R"은 데이터 항목의 순서가 뒤집힙니다. 따라서, "R"을 카운트하고 deque의 앞 쪽에서 삭제 작업을 수행할 것인지 뒤 쪽에서 삭제 작업을 수행할 것인지 결정합니다.
• 미리 카운트한 "R" 횟수를 통해 deque 컨테이너의 항목들을 순선대로 나열할 경우 begin()과 end()를 활용해 컨테이너를 순회하며, 반대로 역순으로 나열할 경우  rbegin()과 rend()를 활용해 컨테이너를 순회합니다.

 

#2. 코드

1. 코드

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

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    int T,N;

    cin >> T;

    while(T--)
    {
        string orders, numStr;
        bool reverse = false, error = false;
        deque<int> dq;

        cin >> orders;
        cin >> N;
        cin >> numStr;

        string num = "";
        for(int i=0; i<numStr.length(); i++)
        {
            if(isdigit(numStr[i]))
            {
                num += numStr[i];
            }
            else if(numStr[i] == ',' || numStr[i] == ']')
            {
                if(!num.empty())
                {
                    dq.push_back(stoi(num));
                    num.clear();
                }
            }
        }

        for(const auto& order : orders)
        {
            if(order == 'R')
            {
                reverse = !reverse;
            }
            else
            {
                if(dq.empty())
                {
                    error = true;
                    break;
                }
                else
                {
                    reverse ? dq.pop_back() : dq.pop_front();
                }
            }
        }
        if(!error)
        {
            cout << '[';
            if(!dq.empty())
            {
                if(reverse)
                {
                    for(auto it=dq.rbegin(); it!=dq.rend(); ++it)
                    {
                        cout << *it;
                        if(it != dq.rend()-1)
                            cout << ',';
                    }
                }
                else
                {
                    for(auto it=dq.begin(); it!=dq.end(); ++it)
                    {
                        cout << *it;
                        if(it != dq.end()-1)
                            cout << ',';
                    }
                }
            }
            cout << ']' << '\n';
        }
        else
        {
            cout << "error\n";
        }
    }

}