[baekjoon] AC 5430 (C++)

5430번: AC (acmicpc.net)

5430번: AC

---

접근 방법

알고리즘 : 덱

 

테스트 케이스를 출력하는 것까지는 성공했지만, 시간초과 발생.

N이 100,000개일때 예상은 했지만 최적화 시킬 수 있는 방법을 생각하지는 못했다.

 

reverse 함수를 최대한 요소를 줄이고 진행하는 방법으로 확인.

---

C++ 

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

int main()
{

  freopen("input.txt", "r", stdin); //제출 시 삭제
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

  int t;
  cin>>t;


  while(t--){
    string cmd,arr;
    int n;
    cin>>cmd;
    cin>>n;
    cin>>arr;

    deque<int>dq;
    if(n==0||cmd==""){
      cout<<"error"<<"\n";
    } else{

    for(char a : arr){
      if(a =='['||a==']'||a==','){
        continue;
      } else{
        dq.push_back(a-'0');
      }
    }

    for(char a:cmd){
      if(a == 'R'){
        reverse(dq.begin(),dq.end());
      }
      if(a == 'D'){
        if(!dq.empty()) dq.pop_front();
      }
    }

    if(dq.empty()){
      cout<<"error"<<"\n";
    } else{
      cout<<"[";
      for(int i=0;i<dq.size();i++){
        if(i == dq.size()-1){
          cout<<dq[i];
        } else{
        cout<<dq[i]<<",";
        }

      }
      cout<<"]"<<"\n";
    }
    }



  }
}

 

---

C++ 정답코드

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

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

void print_result(deque<int>& d){
  cout << '[';
  for(int i = 0; i < d.size(); i++)
  {
    cout << d[i];
    if(i+1 != d.size())
      cout << ',';
  }
  cout << "]\n";
}

int t;
int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> t;
  while(t--){
    deque<int> d;
    int rev = 0;
    int n;
    bool isWrong = false;
    string query, tmp;
    cin >> query;
    cin >> n;
    cin >> tmp;
    parse(tmp, d);
    for(char c : query)
    {
      if(c == 'R')
        rev = 1 - rev;
      else{
        if(d.empty()){
          isWrong = true;
          break;
        }
        if(!rev) d.pop_front();
        else d.pop_back();
      }
    }
    if(isWrong)
      cout << "error\n";
    else{
      if(rev) reverse(d.begin(), d.end());
      print_result(d);
    }
  }
}