[BOJ] C++ 5430 AC - 부분 문자열 찾기

5430번: AC

예제

4
RDD
4
[1,2,3,4]
DD
1
[42]
RRD
6
[1,1,2,3,5,8]
D
0
[]

ans :
[2,1]
error
[1,2,3,5,8]
error

---

문제의 포인트는 생각보다 여러 가지가 있었다.

1. [1,2,3] 형태의 데이터를 가공하여 배열에 넣어야 한다. 처음부터 빈 배열이 들어오는 경우 예외 처리를 잘해줘야 한다.

2. 배열의 앞과 뒤에서 삭제가 빈번히 일어나므로 deque 자료형을 쓰는 편이 유리하다.

3. 빈 배열에 대해 D 연산을 수행하면 error를 출력하지만 R 연산은 수행해도 error를 출력하지 않는다.

4. R 연산이 들어올 때마다 reverse() 연산을 수행하면 시간복잡도가 굉장히 커지므로 신경써서 처리해줘야 한다.

 

1번 포인트는 문자열을 토큰화시켜서 배열에 넣는 방식으로 처리했다.

string full_str, token = "";
cin >> full_str; //[1,2,3]의 형식으로 저장되어 있다.
for (int i = 0; i < full_str.length(); i++)
{
    if (isdigit(full_str[i]))
        token += full_str[i];
    else
    {
        if (!token.empty())
        {
            arr.push_back(stoi(token));
            token = "";
        }
    }
}

3번 포인트는 명령들이 저장되어있는 문자열 p를 순회할 때 D연산 차례에서 error_flag를 두고, 비어있다면 error_flag를 true로 바꿔서 D연산을 수행하지 않는 방식으로 처리했다. 여기서 break를 넣는 타이밍을 조심해야 한다. R연산에 error_flag를 체크하면 빈연산에 대해 reverse를 수행하지 않고 error를 출력하므로 틀리게 된다.

 

4번 포인트는 R연산이 들어올때마다 reverse를 수행하는 것이 아니라, reverse_flag를 두고, 들어올 때마다 값을 바꿔주는 것으로 처리했다. reverse_flag가 true라면 D연산을 수행할 때 맨 뒤의 원소를 삭제하면 된다. 

 

Out Of Bounds 오류와 시간초과를 내기 쉬운 문제이므로 조심해서 풀고 제출하기전에 반례를 많이 넣어보는 것이 좋다.

/** 문자열 5430 AC **/
#include <iostream>
#include <deque>
#include <algorithm>
#include <string>
using namespace std;

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

    int T;
    cin >> T;
    while (T--)
    {
        // 수행할 함수 입력받기
        string p;
        cin >> p;

        int n;
        cin >> n;
        deque<int> arr;
        bool reverse_flag = false, error_flag = false;
        string full_str, token = "";
        cin >> full_str; //[1,2,3]의 형식으로 저장되어 있다.
        for (int i = 0; i < full_str.length(); i++)
        {
            if (isdigit(full_str[i]))
                token += full_str[i];
            else
            {
                if (!token.empty())
                {
                    arr.push_back(stoi(token));
                    token = "";
                }
            }
        }
        for (auto x : p)
        {
            if (x == 'R')
            {
                if (reverse_flag)
                    reverse_flag = false;
                else
                    reverse_flag = true;
            }
            else
            {
                if (!error_flag)
                {
                    if (arr.empty())
                    {
                        error_flag = true;
                        break;
                    }
                    if (reverse_flag)
                        // 배열이 뒤집힌 상태라면 맨 뒤 삭제
                        arr.pop_back();

                    else
                        arr.pop_front();
                }
            }
        }
        if (error_flag)
            cout << "error\n";
        else
        {
            if (arr.empty())
                cout << "[]\n";
            else
            {
                if (reverse_flag)
                    reverse(arr.begin(), arr.end());
                cout << "[";
                for (int i = 0; i < arr.size() - 1; i++)
                    cout << arr[i] << ",";
                cout << arr.back() << "]\n";
            }
        }
    }
}