문제

문제 링크

해설

• 이 문제는 시간 내 풀이하는 조건이 가장 까다로운 문제입니다.
• 문제 마지막 조건 ('전체 T에 주어지는 p + n <= 70만')에 따라 반드시 O(n) ~ O(nlog(n))에 풀어야 합니다.
• 함수 R(뒤집기)이 이 문제의 함정입니다.
  • STL <algorithm> 헤더파일의 reverse()를 떠올리셨다면 이 문제의 함정에 걸리셨습니다.
  • 아쉽게도 reverse() 함수는 시간복잡도가 O(n)인 함수입니다. (정확히는 T(N/2))
    
  • 따라서 함수 R이 p개 존재한다면 (e.g. RRRRRRRR...) 전체 프로그램의 시간복잡도가 O(n²)입니다.
    
  • p + n이 70만이므로 이 문제를 1초내로 풀 수 없습니다.
• std::deque<int>을 사용하면 함수 R과 D를 O(1)로 처리할 수 있습니다.
  1. 먼저 최초 입력 배열을 deque에 입력받습니다.
  2. 함수 D 명령은 '가장 앞 원소를 삭제'하는 것이므로 pop_front() 함수로 맨 앞 원소를 O(1)에 삭제할 수 있습니다.
  3. 함수 R 명령은 '배열을 뒤집는 것'이지만, 실제로 뒤집지 않고, bool타입 플래그 변수를 반댓값으로 바꿀 것입니다. (NOT 연산)
  4. 다음에 만나는 함수 D 명령은 플래그 변수에 따라 마치 배열을 뒤집은 것 마냥 맨 뒷 원소를 pop_back() 함수로 O(1)에 삭제할 것입니다.
  5. 2~4번 과정을 p번 반복합니다.
  6. 모두 종료됐다면, 플래그 변수의 결괏값을 검사합니다. 만일 true라면, 최종 결과는 배열을 뒤집은 형태여야 하므로 이때 딱 한 번 reverse() 함수를 사용합니다.
• 물론 C-스타일 배열, std::array<int>, std::vector<int>보다 std::deque<int>는 메모리 연속성을 보장하지 않기 때문에 캐시를 제대로 활용할 수는 없어서 성능면에서는 떨어질 수 있겠지만, 얻는 이득이 훨씬 큽니다.

코드

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

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int N;
        string cmd, arrStr;
        cin >> cmd >> N >> arrStr;

        int num = 0;
        deque<int> arr;
        for (const char& c : arrStr) {
            if (c == '[' || c == ']') continue;
            if ('0' <= c && c <= '9') num = (10 * num) + (c - '0');
            else { arr.push_back(num); num = 0; }
        }
        if (num) arr.push_back(num);    // 마지막 숫자 처리

        bool err = false, rev = false;
        for (const char& c : cmd) {
            if (c == 'R') rev = !rev;
            else {
                if (arr.empty()) { err = true; break; }
                (rev) ? arr.pop_back() : arr.pop_front();
            }
        }

        if (err) cout << "error\n";
        else {
            if (rev) reverse(begin(arr), end(arr));
            cout << "[";
            for (size_t i = 0, size = arr.size(), commaLimit = arr.size() - 1; i < size; ++i) {
                cout << arr[i];
                if (i < commaLimit) cout << ",";
            }
            cout << "]\n";
        }
    }
}

소스코드 링크

• 이 문제는 출력 형태가 [, , , ,] 꼴로 정해져 있기 때문에 이 부분에서 많이 실수가 발생할 수 있습니다.
• (배열크기 - 1)개 콤마를 출력하기 위해 for문 내부에 if문을 사용했습니다.
• 이 문제에서 가장 큰 논란거리는 '배열에 아무것도 없을 때의 함수 R 결과를 어떻게 출력할 것인지?' 입니다. 이 부분이 문제에 명확히 언급돼있지 않기 때문에 많은 분이 논쟁이 오고간 것 같습니다.
• 아무것도 없을 때는 [] ← 빈 대괄호를 출력해야 합니다.

결과