C++ 백준 5430 (AC)

백준 5430 (AC)

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

5430번: AC

---

deque를 이용해 풀 수 있는 문제였다.

deque에 대한 이해가 없다면 구글링을 해서 알아오도록 하자.

 

또한 입력이 [1,2,3]과 같이 숫자만 주어지는게 아니기 때문에 이를 처리하는 과정이 살짝 귀찮았다.

 

설명

---

수열을 저장 후 뒤집기와 pop을 반복하는 문제였다.

그러나 뒤집기를 할 때 algorithm헤더파일에 존재하는 reverse함수를 쓰게 될 경우 이 함수는 O(N)의 시간복잡도를 갖기 때문에 시간초과가 날것이라는 생각을 했다.

 

그럼 어떻게 하면 될까?

사실 수열 뒤집기는 눈에 보이기 위함이지 거꾸로 생각하면 O(N)의 시간을 소요해 뒤집을 필요가 없다.

[1,2,3]이라는 수열을 뒤집어야 한다면 뒤집지 않고 거꾸로 읽으면 되는거 아닌가?

 

때문에 push와 pop을 앞뒤에서 할 수 있는 자료구조 duque가 필요하다.

'R'이 입력되면 지금이 정방향인지 역방향인지만 알고 있고 그 방향성에 따라 앞에서 push와 pop을 할지 또는 뒤에서 push와 pop을 할지 결정하면 되는 문제였다.

 

구현

---

 

#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
using namespace std;
int main(){
    ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int t,n;
    cin>>t;
    for(int i=0;i<t;i++){
        bool err=false;
        deque <int> arr;
        string cmd,input;
        cin>>cmd;
        cin>>n;
        cin>>input;
        string tmp="";
        if(n!=0){
            for(int j=0;j<input.length();j++){
                if(input[j]=='[' || input[j]==']' || input[j]==','){
                    if(input[j]!='[') arr.push_back(stoi(tmp));
                    tmp="";
                    continue;
                }
                tmp+=input[j];
            }
        }
        int rev = 1;
        for(int j=0;j<cmd.length();j++){
            if(cmd[j]=='R'){
                rev *= -1;
            }
            else{
                if(arr.size()==0) {
                    cout<<"error"<<"\n";
                    err=true;
                    break;
                }
                if(rev==1) arr.pop_front();
                else arr.pop_back();
            }
        }
        if(!err){
            cout<<"[";
            if(rev==1){
                while(!arr.empty()){
                    if(arr.size()!=1) cout<<arr.front()<<",";
                    else cout<<arr.front();
                    arr.pop_front();
                }
            }
            else{
                while(!arr.empty()){
                    if(arr.size()!=1) cout<<arr.back()<<",";
                    else cout<<arr.back();
                    arr.pop_back();
                }
            }
            cout<<"]\n";
        }
    }
    return 0;
}

reverse함수를 써서 해보지는 않았는데 아마 시간초과가 나지 않을까..?