[baekjoon 백준] 5430 - AC : c++ 문제풀이

이젠 골드 이상 문제만 풀기로 마음먹었다...!

 

1. 필요한 자료구조가 무엇인가?

 : 처음에는 delete가 앞에서만 이루어 지길래 queue인 줄 알았으나... "reverse하려면 queue 뒤에서 부터 숫자를 빼고 새로운 queue에 차곡차곡 넣어줘야 하잖아??" <- 반은 맞고 반은 틀림ㅋㅋㅋ

그럼 이 문제는 deque을 활용해야 한다

(Stack구조는 push를 하고 pop을 할 때 맨 마지막에 들어온 요소부터 빠져나가고(Last In First Out), Queue구조는 맨 처음 들어온 요소부터 빠져나간다(First In First Out). 하지만 Deque는 앞 뒤로 모두 push, pop이 가능한 구조라고 보면 된다.)

 

그래서 deque를 사용하고, reverse 함수와 delete 함수를 따로 빼서 구현해봤다.

deque<int> reverse(deque<int>& q){
  deque<int> r; //새로운 deque생성 후에 q맨뒤에서 하나씩 뽑아넣기
  while(!q.empty()){ 
    r.push_back(q.back());
    q.pop_back();
  }
  return r;
}

int del(deque<int>& q){
  if (q.empty()){ //비어있는경우 0을 retrun해 error처리
    return 0;
  }
  else{
    q.pop_front(); //deque 맨 앞 pop
    return 1;
  }
}

//사용한 reverse 함수와 delete 함수

결과도 잘 나왔으나 시간초과!...

생각해보니 그냥 하나의 배열을 reverse하는 과정을 저따구로 구현하는 건 시간낭비가 맞았다. 어차피 출력만 반대로하면 되는 걸..? deque를 쓰면 delete도 앞뒤로 다 되잖아...!

그래서 함수 두 개는 날려버리고 reverse 상태인지 아닌지 구분하는 변수 하나만 더 추가해 새로 수정하고 구현했다. 

#include <iostream>
#include <string>
#include <deque>
using namespace std;

int main() {
  int n, len; //테케 수, 배열 크기
  string p, v; //함수 p, 배열 입력받는 v
  deque<int> d; //deque
  cin >> n;
  for (int i=0; i<n;i++){
    d.clear(); //deque 초기화
    cin >> p; 
    cin >> len;
    cin >> v;
    int idx =1; //입력받은 v deque로 처리
    string stmp=""; //임시 문자열
    int res = 1; //index 1부터 읽기
    //stmp에 숫자 문자열로 저장했다가 쉼표만나면 deque에 push
    while(v[idx] != ']'){ 
      if(v[idx] == ','){ 
        d.push_back(stoi(stmp)); 
        stmp="";
      }
      else{
        stmp += v[idx];
      }
      idx++;
    }
    //마지막 숫자 처리
    if(stmp!=""){d.push_back(stoi(stmp));}
    
    int r=0;//reverse on/off 키
    for(int j =0; j<p.length();j++){
      if(p[j]=='R'){
        r = !r;
      }
      else{
        if(d.empty()){
          cout <<"error"<<endl;
          res = 0; //result가 false ->에러
          break;
        }
        else{ //reverse on이면 뒤에서, off면 앞에서 pop
          if(r){
            d.pop_back();
          }
          else{
            d.pop_front();
          }
        }
      }
    }
    //result true
    if(res){ 
      cout << "[";
      if (r){
        //reverse on 경우 역순 출력
        for(auto it=d.rbegin(); it != d.rend(); it++){
          if(it == d.rend()-1){
            cout<< *it;
          }
          else{
            cout << *it << ",";
          }
        }
      }
      else{//reverse off 경우 순차 출력
        for(auto it=d.begin(); it != d.end(); it++){
          if(it == d.end()-1){
            cout<< *it;
          }
          else{
            cout << *it << ",";
          }
        }
      }
      
      cout << "]" << endl;
    }
  }
  return 0;
}

 deque를 쓰면서 새롭게 안 사실은 iterator로 begin()/end() 말고도 rbegin()/rend()(reverse)를 쓸 수 있다는 것이다. 넘 굿~....

 

아쉬운 점은 배열 입력받아서 처리하는 과정을 좀 복잡하게 구현한 것 같다...