[BOJ] 5430: AC

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

 

 

 

 

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

void parse(string& arr, deque<int>& dq) {
  int num = 0;
  for (int i = 1; i + 1 < arr.size(); i++) {
    if (arr[i] == ']') break;
    if (arr[i] >= '0' && arr[i] <= '9')
      num = num * 10 + (arr[i] - '0');
    else {
      dq.push_back(num);
      num = 0;
    }
  }
  if (num != 0) dq.push_back(num);
}

void print_deque(deque<int>& dq) {
  cout << '[';
  for (int j = 0; j < dq.size(); j++)
    cout << dq[j] << (j + 1 != dq.size() ? "," : "");
  cout << ']' << '\n';
}

int t, n;
string p, arr;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> t;
  for (int i = 0; i < t; i++) {
    deque<int> dq;
    int rev = 0;
    int error = 0;
    cin >> p >> n >> arr;
    parse(arr, dq);

    for (char f : p) {
      if (f == 'R')
        rev = 1 - rev;
      else {
        if (dq.empty()) {
          error = 1;
          break;
        }
        if (rev)
          dq.pop_back();
        else
          dq.pop_front();
      }
    }
    if (error)
      cout << "error" << '\n';
    else {
      if (rev) reverse(dq.begin(), dq.end());
      print_deque(dq);
    }
  }
}

처음엔 스택을 사용해서 R연산을 처리했는데, 이렇게 했더니 시간 초과가 됐다.

O(n)에서 시간 초과가 됐으니 이보다 더 빠른 방법을 찾아야 했다.

 

이 문제는 R연산과 D연산 두 가지만 존재한다.

입력으로 [1, 2, 3, 4, ..., 10]가 주어졌다고 가정할 때,

D연산을 수행하면 [2, 3, 4, ..., 10]이고,

R연산과 D연산을 연속으로 수행하면 [9, 8, 7, ..., 1]이 된다.

 

즉 R연산을 수행한 후 D연산을 수행하는 건 배열의 가장 뒤의 원소를 삭제하는 것과 같다.

결국 이 문제는 배열의 가장 앞과 가장 뒤의 원소를 삭제하는 연산을 처리하면 되므로 deque를 사용해서 해결할 수 있다.

 

parse 함수는 입력으로 주어진 배열을 dq에 할당하는 역할을 한다.

arr[i]가 digit인 경우 int로 변환해서 num에 저장하고, arr[i]가 '(쉼표)인 경우 num을 dq에 push한다.

arr[i]가 ](닫는 대괄호)라면 반복문을 종료하고 미처 넣지 못한 num을 push해준다.

여기서 (num != 0)로 따로 분기처리 해주는 이유는 배열이 empty일 때 dq에 아무것도 할당해주지 않기 위해서다.

 

이제 p에서 수행할 함수를 하나씩 가져와서 처리해준다.

f가 R일 경우 reverse해야 하는데, 위에서 봤던대로 dq를 뒤집지 않고 맨 뒤 원소만 삭제해도 되기 때문에 rev만 체크해준다. 

=> 여기서 rev = 1 - rev로 작성한 이유는 rev가 1이라면 0이되고, 0이라면 1로 바뀌기 때문이다.

 

f가 D일 경우 원소를 삭제해야 하는데 먼저 rev를 체크해야 한다.

rev가 0이라면 뒤집히지 않았으므로 dq.pop_front()를 실행하고,

rev가 1이라면 뒤집힌 것이므로 dq.pop_back()을 실행한다.

이때 dq가 empty라면 error가 발생한 것이므로 error를 1로 바꿔주고, 반복문을 종료한다.

 

p에 열거된 함수 실행이 끝났으면 dq를 print 해야한다.

이때 error가 1이라면 "error"를 출력하고, 아니라면 print_deque 함수를 호출한다.