[BOJ] 백준 5430 AC

[BOJ] 백준 5430 AC

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


이 문제는 배열이 주어졌을때 R 입력은 순서를 바꾸는 것, D는 맨 앞의 문자를 지우는 것으로 명령을 수행하는 문제 입니다.
여기서 중요한 것은 입력 배열이 최대 70만이라는 것인데, 많은 입력이 주어졌고, 명령이 RRRRRRRR.... 로 주어졌다면 일반적으로 역순으로 바꾸는 로직은 많은 시간복잡도를 필요로 합니다.


따라서, 덱을 이용하여 순서를 바꾼 듯 한 효과를 주는것이 중요한 문제 입니다.


소스코드 :

#include 
#include 
#include 
using namespace std;

// 덱에 저장한 정수들을 s의 명령에 따라 변환 및 출력하는 함수 Func1.
void Func1(string s, deque dq) {
 
 // 변환명령 R이 입력될 경우를 판단할 변수 isD 선언.
 bool isD = false;
 bool flag = false;  // error 항목일 경우 출력을 위한 변수 flag 선언.
 
 for (int i = 0; i < s.length(); i++) {
  if (s[i] == 'R') {

   // R이 입력 될 경우 변수 On/Off
   isD = !isD;
  }
  else if (s[i] == 'D') {
   if (!dq.empty()) {
    
    // 홀수번째 입력의 경우 : 맨 뒤의 원소 POP, 짝수번째 입력의 경우 : 맨 앞의 원소 POP.
    if(isD) dq.pop_back();
    else dq.pop_front();
   }
   else {

    // 원소가 없는데 pop 명령이 떨어질 경우 error발생
    flag = true;
    cout << "error" << endl;
    break;
   }
  }
 }

 // error가 아닌경우 출력.
 if (!flag) {
  int dsize = dq.size();
  cout << '[';

  //원소가 없을 경우, 바로 괄호 닫는다.
  if (dsize == 0) cout << ']'<> T; cin.ignore();
 while (T--) {
  string s; cin >> s; cin.ignore();
  int max; cin >> max; cin.ignore();
  string arr; cin >> arr; cin.ignore();
  deque dq;

  // 입력받은 배열의 길이를 담을 변수 arrlength 선언.
  int arrlength = arr.length();
  for (int i = 0; i < arrlength; i++) {
   
   //arr[i]가 숫자일 경우 ' , ' , ' ] ' 만나기 전까지의 숫자들을 stmp에 저장.
   if (isdigit(arr[i])) {
    string stmp = "";
    int tmp = i;
    while (tmp < arrlength) {
     if (arr[tmp] == ',' || arr[tmp] == ']') {
      break;
     }
     else {
      stmp += arr[tmp];
     }
     tmp++;
    }
    // 저장한 stmp 문자열을 정수로 변환 후 덱에 Push
    dq.push_back(stoi(stmp));
    i = tmp;
   }
   
  }
  Func1(s, dq);
 }
}