[BOJ] 백준 5430 AC c++ 코드 / 풀이

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

5430번: AC

 

 

문제해설

한줄로 된 명령어를 받아서 입력 받은 배열에 연산을 진행 한 후 결과 값을 출력하는 문제

배열은 숫자 배열이고, R 함수는 배열의 순서를 뒤집고, D 함수는 배열의 첫 번째 요소를 버림

만약 배열이 비어 있는 상태에서 D 함수를 호출하면 에러가 발생

ex)

[1,2,3,4] => R 명령어 실행 시 [4,3,2,1]

[1,2,3,4] => D 명령어 실행 시 [2,3,4]

 

 

문제풀이

처음에는 문제를 단순하게 생각하고 문자열로 입력 받은 배열을 파싱해서 vector에 저장

이후 R 명령어일 땐 vector의 reverse를 실행하고 D 명령어 일땐 v.begin을 지우는 식으로 구현 했었으나...

깔끔하게 시간초과 발생!

솔직히 그냥 구현하면서도 이게 시간초과 안날까 싶긴 했었기 때문에 빠르게 포기

배열을 종이에 그려놓고 이거저거 해보다 보니 덱으로 풀면 간단하지 않을까 라는 생각이 들었음

입력 값 그대로 덱1에 저장해놓고, 덱1을 뒤집은 덱2를 선언하여 저장

즉 [1,2,3,4]가 입력됐을때 덱1 = 1,2,3,4 덱2는 4,3,2,1이 저장된 상태

이 상태에서 현재 덱이 뒤집힌 상태인지 아닌지 판단하는 bool 변수 하나 놓고 R명령어가 입력 될때마다 값을 바꿔주며 덱의 상태를 저장

D가 입력 될 때는 덱1에서는 맨 앞의 요소, 덱2에서는 맨 뒤의 요소가 삭제되도록 구현, 뒤집힌 상태일 경우 이와 반대로 삭제

 

코드설명

parsing 함수로 입력받은 문자열을 덱에 할당

주어진 함수 'p'를 문자 하나씩 읽어가며 명령어 실행

R 입력시 덱을 뒤집는 플래그 rev의 값을 토글, D 일 경우 덱에서 해당 요소를 제거

이때 에러 체크, 덱이 비어 있을 때 D 실행 시 에러 출력

rev 플래그 상태에 따라 결과를 출력하도록 동작

reverse()함수 등으로 뒤집을 때와 다르게 이렇게 동작 할 경우 뒤집는 연산을 O(1)의 시간 복잡도로 처리가 가능함

 

코드

#include <bits/stdc++.h>
#define PRESET ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

/*
    덱 두개를 놓고 하나에는 원본, 나머지 하나엔 뒤집어서 넣기
    D가 들어오면 원본에선 앞에서 제거하고 다른거에선 뒤에서 제거
    R은 들어올때마다 flag하나 놓고 0, 1 바꿔주면 될듯
*/

deque<int> d1;
deque<int> d2;

void parsing(string str){
    stringstream ss(str.substr(1, str.length() - 2)); // 대괄호 제거
    int num;
    char dot;

    while(ss >> num) {
        d1.push_back(num);
        d2.push_front(num);
        ss >> dot;
    }
}



int main(){
    PRESET;

    int t;
    
    cin >> t;

    while(t--){
        vector<int> ans;
        string p, str;
        bool rev = false, flag = false;
        int n;
        d1.clear();
        d2.clear();

        cin >> p >> n >> str;

        if(n) parsing(str);
        
        for(auto c : p){
            if(c == 'R'){
                rev = rev ? false : true;
            }
            else{
                if(d1.empty()){
                    cout << "error\n";
                    flag = true; // error 판별
                    break;
                }
                else{
                    if(rev){ // 뒤집힌 상태
                        d1.pop_back();
                        d2.pop_front();
                    }
                    else {
                        d1.pop_front();
                        d2.pop_back();
                    }
                }
            }
        }
        if(flag) continue;


        else{
            cout << "[";
            if(!rev){
                for(int i = 0; i < d1.size(); i++){
                    cout << d1[i];
                    if(i == d1.size() - 1) break;
                    cout << ",";
                }
            }
            else {
                for(int i = 0; i < d2.size(); i++){
                    cout << d2[i];
                    if(i == d2.size() - 1) break;
                    cout << ",";
                }
            }
            cout << "]\n";
        }
    }
}