(백준/C++) 5430번_AC

5430번: AC (acmicpc.net) 문제는 양방향 큐인 덱(Deque)을 이해하기 매우 좋은 문제라고 생각합니다.

그렇게 생각하는 이유중 하나는 이 문제에서

“함수 R은 배열에 있는 수의 순서를 뒤집는 함수이고, D는 첫 번째 수를 버리는 함수이다.”

라는 부분 때문입니다.

임의 접근 가능한 컨테이너를 잘 쓰거나 양방향 컨테이너를 잘 쓴다면, 순서를 뒤집는 문제에서 요소들을 뒤집는데 시간을 소비하지 않아도 됩니다.

예를 들어, 일반적인 큐(Queue)로 순서 뒤집기 문제를 푼다면, 스택을 이용해야 할 것입니다. (어디까지나 단방향 컨테이너만 쓴다는 조건이라면… 말이죠.)

하지만, 덱(Deque)의 경우에는 뒤에서 순차적으로 접근하는 기능을 가지고 있기 때문에, 컨테이너 내부의 요소를 직접 뒤집지 않아도 뒤집은 것처럼 사용할 수 있습니다.

주의 사항

이 문제에서 주어지는 입력은 [1,2,3,4] 와 같은 형태로 주어집니다. 따라서 이 문자열에서 정수만을 추출하는 방법을 고민해야 합니다.

풀이 과정

저는 위 주의사항에 적혀있는 내용인 [1,2,3,4] 와 같은 문자열에서 정수만을 추출하기 위해 erase()와 getline()을 사용 했습니다.

1. erase()와 remove()를 사용하지 않아도 각 괄호들을 삭제 시킬 수 있지만, 문자열 삭제에 대한 함수를 다루기 위해 사용해봤습니다.
   • remove()는 원하는 위치에서 지정한 문자를 찾은 경우, 한 칸 앞으로 문자열들을 이동시킵니다. (결론적으로 지정한 문자를 지워주는 효과를 얻습니다.)
     그리고 원래 문자열의 끝을 가리키는 새로운 “끝”을 가리키는 반복자를 반환합니다. (컨테이너의 크기가 변경되지 않았기 때문에, 삭제 후 삭제가 필요한 요소의 위치를 반환한다고 생각하면 됩니다.)
   • 따라서, 원래 문자열의 끝을 가리키는 반복자를 가지고 erase()를 호출해 컨테이너의 남은 부분을 삭제시켜 주면, 실제로 문자를 삭제한 효과를 얻습니다.
2. getline()은 기본적으로 \n를 구분자로 사용해 문자열을 입력받지만, 세 번째 인자로 구분자를 지정해주면 그 문자를 기준으로 문자열을 입력받습니다.
   • 입력을 필요한 만큼 따로 해주지 않기 때문에, 새로운 문자열 스트림을 stringstream으로 만들어 문자열을 스트림에 저장하면, getline()으로 반복해서 받아올 수 있습니다.

#include <iostream>
#include <deque>
#include <sstream>
#include <algorithm>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    int T;
    cin >> T;
    while (T--)
    {
        string func;
        deque<int> nums;
        int n;
 
        //함수 저장
        cin >> func;
 
        //정수 저장
        {
            cin >> n;
            string tmp;
            cin >> tmp;
 
            tmp.erase(remove(tmp.begin(), tmp.end(), '['), tmp.end());
            tmp.erase(remove(tmp.begin(), tmp.end(), ']'), tmp.end());
 
            stringstream ss(tmp);
 
            while (getline(ss, tmp, ',') && n--)
                nums.push_back(stoi(tmp));
        }
        //함수 실행
        bool reverseFlag = false;
        bool errFlag = false;
        for(const char& f : func)
        {
            //D(첫번째 수 버리기), R(순서 뒤집기)
            if(f == 'D')
            {
                if(nums.empty())
                {
                    errFlag = true;
                    break;
                }
                if (reverseFlag) nums.pop_back();
                else nums.pop_front();
            }
            else if(f == 'R')
            {
                reverseFlag = !reverseFlag;
            }
        }
        //출력
        if (errFlag)
        {
            cout << "error\n";
        }
        else
        {
            cout << '[';
            if(reverseFlag)
            {
                while (!nums.empty())
                {
                    cout << nums.back();
                    nums.pop_back();
                    if (!nums.empty()) cout << ',';
                }
            }
            else
            {
                while (!nums.empty())
                {
                    cout << nums.front();
                    nums.pop_front();
                    if (!nums.empty()) cout << ',';
                }
            }
            cout << "]\n";
        }
    }
}