백준 5430번, AC

백준 5430번 c++ 문제풀이

문제:

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

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

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

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

풀이:

1. “[1,2,3]” 이런 식으로 입력 되어져 있는 문자열에서 숫자를 분리해 순서대로 덱에 저장한다.
2. 명령어를 읽은 후 R을 읽으면 reverse = true, D를 만나면 reverse의 값에 따라 pop_back을 할지, pop_front를 할지 결정한다.
3. 덱이 비워져있는 상황에서 D명령어를 읽으면 error = true로 바꿔준 뒤, error 출력.
4. 출력 시 error가 true이면 출력하지 않는다.
5. error가 fasle 이면 출력하는데 reverse가 true 인지, false인지에 따라 출력 순서를 바꿔준다.

처음 코드를 작성할 때 vector를 이용해서 명령어의 명령을 수행하는 코드를 작성했다.

 for (int j = 0; j < com.length(); j++) {
        if (com[j] == 'R') {
            reverse(v.begin(), v.end());
        } else if (com[j] == 'D') {
            if (v.size() == 0) {
                cout << "error"
                     << "\n";
                error = true;
                break;
            } else {
                v.erase(v.begin());
            }
        }
    }

이 코드의 잘못된 점을 찾지 못해 좀 고생했던 것 같다.
출력은 잘되었지만 제출할 때 계속 시간초과가 나는게 문제였다..

위 코드의 잘못된 점은 명령을 읽을 때 마다 명령을 수행해서, 시간 복잡도가 O(n)이었다는 것이다.

문제를 해결하기 위해서 덱으로 코드를 짜고, 시간 복잡도를 O(1)로 바꾸니 시간초과가 되지 않았다.
밑의 코드가 다시 작성한 코드이다.

코드:

#include <iostream>
#include <algorithm>
#include <deque>
#include <string>
#include <cmath>

using namespace std;

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    
    cin >> t;

    for(int i=0;i<t;i++){
        string com;
        string lis;
        string num = "";
        bool error = false; //에러인지 판별
        bool reverse = false; //역순인지 판별
        int n=0;
        deque <int> dq;
        cin >> com;
        cin >> n;

        cin >> lis;

        for(int i=0;i<lis.length();i++){
            if(isdigit(lis[i])){
                num+=lis[i];
            }
            else{
                if(!num.empty()){
                dq.push_back(stoi(num));
                num = "";
                }
            }
        }
    

        for(int j=0;j<com.length();j++){
            if(com[j] == 'R'){
                if(reverse){
                    reverse  = false;
                }
                else{
                    reverse = true;
                }
            }
            else if(com[j] == 'D'){
                if(dq.size()==0){  //덱이 비워져 있다면
                    cout << "error" <<"\n";
                    error = true;
                    break;
                }

                if(reverse){
                    dq.pop_back();
                }else{
                    dq.pop_front();
                }
            }
        }
        if(!error){
            if(dq.size() == 1){
                cout << "[" << dq[0] << "]\n";
            }
            else{
                if(reverse){
                    cout << "[";
                    for(int i=dq.size()-1;i>=0;i--){
                            if(i==dq.size()-1){
                            cout << dq[i];
                        }
                        else{
                            cout << ',' << dq[i];
                        }
                    }
                    cout << "]\n";
                }else{
                    cout << "[";
                    for(int i=0;i<dq.size();i++){
                        if(i==0){
                            cout << dq[i];
                        }
                        else{
                            cout << ',' << dq[i];
                        }
                    }
                        cout << "]\n";
                }
            }
        }
    }

    
    return 0;
}

감사합니다.