[백준 5430번] AC - C++

문제 접근

처음에는, 그냥 reverse함수를 이용해 뒤집고, 제출하니 시간 초과가 났다. 뒤집을 때 최대 10⁵ 개의 연산을 하고, p의 최대 길이는 10⁵ 이므로, 10¹⁰번의 연산을 수행하게 된다. 따라서 1초 만에 통과하지 못한다.

이 문제는 접근 방식을 바꿔야 하는 문제이다.

뒤집고, 맨 앞의 원소를 제거하는 연산을 => 뒤집지 않고, 맨앞 또는 맨뒤의 원소를 제거하는 것으로 다르게 생각해서 시간 복잡도를 줄여야 한다.

bool변수를 두어, 정방향은 false, 역방향은 true로 두고 뒤집는 연산을 대신하였다.

 

메모

이 문제는 입력을 받는 것도 까다로웠다. '['  ']'  ',' 를 걸러내고 숫자만 받아야 하는데, 받는 수가 최대 3자리임을 고려해야한다. 아래에서는 ',' ']' 일 때, 수를 push 하는 방식으로 구현했다. 받는 자리 수가 한자리 수가 아닐 수 있으므로, 숫자가 연속으로 나오면 전에 숫자에 10을 곱하는 형식으로 해결했다.

 

#include <bits/stdc++.h>
using namespace std;

void solve() {
  int t;
  cin >> t;

  string p, in;
  int n;
  a:
  while(t -- > 0) {
    int cur = 0;
    int len = 0;
    cin >> p;
    cin >> n;
    cin >> in;
    deque<int> d;
    deque<int> temp;
    for(char c : in) { // input
      if(c == '[') {
        continue;
      }
      if(c == ']' || c == ',') {
        if(cur == 0) continue;
        d.push_back(cur);
        cur = 0;
        continue;
        }
      cur = cur * 10 + (c - '0');
      temp.push_back(0);
    }
    bool isError = false;
    bool flag = false;
    for(char c: p) {
      if(c == 'R') { // 뒤집기
        flag = !flag;
      } else if(c == 'D') {
        if(d.empty()) {
          isError = true;
          break;
        }
        if(flag) {
          d.pop_back();
        } else {
          d.pop_front();
        }
      }
    }
    if(isError) {
      cout << "error" << '\n';
    }
    else {  
      cout << '[';
      for(int i = 0; i < d.size(); i ++) {
        if(flag) {
          cout << d[d.size() - 1 - i];
        } else {
          cout << d[i];
        }
        if(i+1 != d.size()) cout << ',';
      }
      cout << ']' << '\n';
    }
  }
}

// ************************************

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  solve();
}