[BOJ/5430/C++] AC

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

문제

선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다.

• 함수 R은 배열에 있는 수의 순서를 뒤집는 함수이고, D는 첫 번째 수를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다.

함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. 예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 수를 버리는 함수이다.

배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램을 작성하시오.

조건

• 첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 최대 100이다.

• 수행할 함수 p가 주어진다. p의 길이는 1보다 크거나 같고, 100,000보다 작거나 같다.

• 배열에 들어있는 수의 개수 n이 주어진다. (0 ≤ n ≤ 100,000)

• [x1,...,xn]과 같은 형태로 배열에 들어있는 정수가 주어진다. (1 ≤ xi ≤ 100)

전체 테스트 케이스에 주어지는 p의 길이의 합과 n의 합은 70만을 넘지 않는다.

풀이

풀이자체는 복잡하진 않지만, 생각해야하는 포인트가 많았던 문제였다. 생각하는 분기점이 많았기 때문에 구현자체가 꽤 오래걸린 문제이다.

완탐이 안되는 이유

• 위 풀이를 완탐으로 정직하게 푼다면, R을 만날 때 배열을 뒤집으면 되는데 수행할 함수 P가 최대 100,000이고, 배열에 있는 개수가 최대 100,000이기 때문에 최악으로 P가 "RRRRR...RR..."와 같이 된다면, 하나의 P당 최대 10만번의 연산이 일어나게 되므로 10^10 ,완탐으로는 풀 수 없게 된다.

따라서, 뒤집는다라는 개념을 다르게 구현을 해야하며, [1,2,3,4]로 주어지는 입력 또한 1,2,3,4 숫자만 뽑아서 deque에 넣어야한다.그리고, 출력기능도 [1,2,3,4]와 같이 출력을 해야한다.

즉, Array를 처리할 Parsing하는 기능, Query(요청한 연산)을 처리하는 기능, 마지막으로 출력하는 기능 3가지 기능을 조건에 맞게 구현하면 된다. 점점 참조자에 익숙해지는것 같다!

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;

void parseArray(string &s, deque<int> &dq)
{
  string tmp = "";
  for (int i = 0; i < s.size(); i++)
  {
    if (isdigit(s[i]))
      tmp += s[i];
    else
    {
      if (!tmp.empty())
      {
        dq.push_back(stoi(tmp));
        tmp = "";
      }
    }
  }
}
void execQuery(string &query, deque<int> &dq, bool &error, bool &reverse)
{
  for (char c : query)
  {
    if (c == 'R')
    {
      reverse = !reverse;
      continue;
    }
    //"D"를 만나는 순간 , 비었다면 error를 출력하고, error를 true로 바꾼다.
    if (dq.empty())
    {
      cout << "error" << '\n';
      error = true;
      return;
    }
    if (reverse)
      dq.pop_back();
    else
      dq.pop_front();
  }
}
void printArray(deque<int> &dq, bool &reverse)
{
  cout << "[";
  if (reverse)
  {
    while (!dq.empty())
    {
      cout << dq.back();
      dq.pop_back();
      if (!dq.empty())
        cout << ",";
    }
  }
  else
  {
    while (!dq.empty())
    {
      cout << dq.front();
      dq.pop_front();
      if (!dq.empty())
        cout << ",";
    }
  }
  cout << "]" << '\n';
}
int main()
{
  fastio;
  int T;
  cin >> T;

  string query;
  int arrlength = 0;
  string arr;
  while (T--)
  {
    deque<int> dq;
    cin >> query >> arrlength >> arr;
    bool error = false;
    bool reverse = false;

    // 배열을 deque 에 넣어주는 과정
    parseArray(arr, dq);
    execQuery(query, dq, error, reverse);
    // 출력하는 부분
    if (!error)
      printArray(dq, reverse);
  }
  return 0;
}