greentea31's Note

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

풀이 과정

배열에 R(뒤집기), D(첫 번째 수 버리기) 연산을 합쳐서 10만 번 이하로 시행할 때, 배열의 최종 결과를 구하는 문제이다.

배열을 뒤집는 연산은 O(N)이고, 첫 번째 수를 버리는 연산도 O(N)이다. 배열이 아닌 큐를 사용하면 첫번째 수를 버리는 연산을 pop()으로 O(1)만에 수행할 수 있으니 큐로 문제를 풀면 좋을 것 같다는 생각이 든다.

그런데 R을 인식했을 때 실제로 배열을 뒤집으면 시간 초과가 발생한다. 배열에 들어있는 수가 문제에서 주어진 최대 값인 10만 개가 주어졌다고 가정하고, 수행할 함수 p가 길이가 10만이라고 해보자. p가 전부 다 R로 꽉 차있어도 실제로 10만 번 뒤집을 필요까지는 없다. R이 2번 연속으로 나오면 아무 연산을 안 해도 2번 뒤집은 것이랑 같은 결과를 내기 때문이다.

따라서 RDRDRDRDRDRD..... RDRDRDRD 이런 식으로 나와서 R이 50000번 나오는 경우가 가장 시간이 오래 걸리는 경우일 것이다. 10만 크기의 배열을 5만 번 뒤집을 때 연산 횟수를 어림잡아 계산하면 10만 * 5만 = 50억인데, 시간제한 1초 내에 50억 번의 연산을 할 수는 없다.

R이 짝수번 연속으로 나올 때 연산을 무시해서 연산 횟수를 줄여도 시간 내에 문제를 해결할 수 없으니 이 문제를 시간 내에 해결하려면 뒤집기 연산이 나왔을 때 배열을 실제로 뒤집으면 안 된다.

배열이 뒤집힌 상태에서 첫 번째 수 버리기 연산을 하는 것은 배열의 마지막 수를 버리는 연산과 같다. 또한 배열이 뒤집힌 상태이면 배열을 역순으로 출력하고, 뒤집히지 않은 상태일 때 그대로 출력한다면 배열을 뒤집지 않고도 첫 번째 수 버리기 연산과 배열의 출력이 이루어 질 것이다.

따라서 배열이 뒤집혔는지를 판단하는 변수 하나를 두고, 변수의 값에 따라 첫번째 수를 버릴지, 마지막 수를 버릴지, 똑바로 출력할지, 반대로 출력할지를 판단해서 문제를 해결할 수 있다. 첫번째 수, 마지막 수를 O(1)로 버릴 수 있는 자료구조는 덱이므로 덱을 사용해서 문제를 해결하였다.

소스 코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <deque>
using namespace std;

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

    int T;
    cin >> T;

    while(T--) {
        deque<int> DQ;
        int t = 0;
        bool errorFlag = false;

        string s;
        cin >> s;

        int num;
        cin >> num;

        string numbers;
        cin >> numbers;


        // 문자열 파싱후 덱에 삽입
        int parse_number = 0;
        for (char let : numbers) {
            if (isdigit(let)) {
                int parse = int(let) - 48;
                parse_number = parse_number * 10 + parse;
            } else {
                if (parse_number == 0) continue;
                DQ.push_back(parse_number);
                parse_number = 0;
            }
        }


        for (char let : s) {
            if (let == 'R') {
                t = (t+1) & 1;
            } else if (let == 'D') {
                if (DQ.empty()) {
                    cout << "error\n";
                    errorFlag = true;
                    break;
                }

                if (t == 0) {
                    DQ.pop_front();
                } else {
                    DQ.pop_back();
                }
            }
        }

        if (errorFlag) continue;

        cout << '[';
        int save_size = DQ.size();

        for (int i = 1; i <= save_size; i++) {
            if (t == 0) {
                cout << DQ.front();
                DQ.pop_front();
            } else {
                cout << DQ.back();
                DQ.pop_back();
            }
            if (i == save_size) break;
            cout << ',';
        }

        cout << "]\n";
    }

    return 0;
}