백준 5430 AC

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

#include <iostream>
#include <vector>
#include <queue>

using namespace std;


int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int t;

    cin >> t;

    for (int test = 0; test < t; test++) {

        string func, sarr;
        deque<int> dq;
        int n;



        cin >> func;

        cin >> n;

        cin >> sarr;

        string temp;

        for (int i = 0; i < sarr.size(); i++) {
            if (isdigit(sarr[i])) {
                temp += sarr[i];

            }
            else {
                if (!temp.empty()) {
                    dq.push_back(stoi(temp));
                    temp.clear();
                }
            }
        }



        bool err = false;
        bool rev = false;

        for (int i = 0; i < func.size(); i++) {

            //뒤집는 함수
            if (func[i] == 'R') {
                rev = !rev;
            } else if (func[i] == 'D') {
                if (dq.empty()) {
                    err = true;
                    break;
                }
                if (rev) {
                    dq.pop_back();
                } else {
                    dq.pop_front();
                }
            }

        }

        if (err) {
            cout << "error";
        } else {
            cout << "[";
            if (!dq.empty()) {
                if (!rev) {
                    for (int i = 0; i < dq.size(); i++) {
                        cout << dq[i];
                        if (i != dq.size() - 1) {
                            cout << ",";
                        }
                    }
                }
                else {
                    for (int i = dq.size() - 1; i >= 0; i--) {
                        cout << dq[i];
                        if (i != 0) {
                            cout << ",";
                        }
                    }
                }
            }
            cout << "]";
        }
        cout << "\n";

    }

    return 0;
}

1. 문제

정수 배열에 연산을 하기 위한 프로그래밍 언어 AC가 있다. 이는 다음과 같은 연산을 지원한다.

• R: 배열의 순서를 뒤집는 함수
• D: 배열의 첫번째 수를 버리는 함수

[1,2,3,4]

함수가 주어지고, 배열의 개수와 배열이 이런 식으로 주어졌을 때, 연산의 결과를 출력하는 문제이다.

2. 풀이

배열이 최대 10만개가 주어지고, 뒤집는 연산이 있으므로 일반적으로 구현하면 시간초과가 난다. 다음과 같은 아이디어를 사용한다.

• 배열의 결과를 출력하는 문제이므로 그 과정에서 배열을 직접 뒤집을 필요가 없다.
• D 연산을 뒤집고 수행하면 배열의 뒤를 지우는 것과 같다.

배열의 앞뒤에서 pop 연산이 일어나므로 deque를 사용한다.

string temp;

for (int i = 0; i < sarr.size(); i++) {
    if (isdigit(sarr[i])) {
        temp += sarr[i];

    }
    else {
        if (!temp.empty()) {
            dq.push_back(stoi(temp));
            temp.clear();
        }
    }
}

 배열을 기호와 함께 입력받으므로 받은 배열을 숫자로 바꾸어 덱에 push한다. 숫자일 경우 임시 문자열에 추가하고, 아닐 경우 ,를 만난 것이므로 덱에 push하고 임시 문자열을 초기화한다.

 

bool rev=false;

//뒤집는 함수
if (func[i] == 'R') {
    rev = !rev;
}

 덱은 앞뒤에서 모두 pop 연산이 가능하므로 reverse 여부만 나타낸다. 두번 뒤집으면 원래 배열과 같이 나오므로 not 연산을 사용한다.

else if (func[i] == 'D') {
    if (dq.empty()) {
        err = true;
        break;
    }
    if (rev) {
        dq.pop_back();
    } else {
        dq.pop_front();
    }

 배열이 비어있을 때 D 연산을 사용하면 에러가 발생하므로 이를 처리한다. 그렇지 않다면 배열이 뒤집혀있지 않을 경우 앞에서 제거, 뒤집혀있을 경우 뒤에서 제거한다.

if (err) {
    cout << "error";
} else {
    cout << "[";
    if (!dq.empty()) {
        if (!rev) {
            for (int i = 0; i < dq.size(); i++) {
                cout << dq[i];
                if (i != dq.size() - 1) {
                    cout << ",";
                }
            }
        }
        else {
            for (int i = dq.size() - 1; i >= 0; i--) {
                cout << dq[i];
                if (i != 0) {
                    cout << ",";
                }
            }
        }
    }
    cout << "]";
}
cout << "\n";

에러가 났을 경우 이만 출력한다. 그렇지 않다면 배열을 출력해야 하는데, 뒤집혀 있을 경우 뒤에서부터 출력한다. 수의 중간에 쉼표를 추가하지만, 배열의 마지막일 경우 출력하지 않는다. 이를 대괄호로 감싸면 정답을 출력할 수 있다.