백준 5430 (AC) C++

문제

5430번: AC

배열을 입력 받고 명령문을 입력받습니다.

명령문중 R은 입력받은 배열을 뒤집는 것이고, D는 배열의 첫번째 원소를 삭제하는 것입니다.

모든 명령어가 끝났을 때 배열을 출력해주는 문제입니다.

 

단순히 알고리즘은 쉬웠습니다. 

자료구조 덱 을 이용해 풀어보았지만 계속 '시간초과' 가 나왔습니다.

 

힌트를 얻어보니 배열을 뒤집는 것은 굳이 뒤집을 필요가 없는 것입니다.

매번 R 명령어를 볼떄 마다 뒤집어주면 시간초과가 나지만 배열의 앞뒤를 체크해주고 

마지막에 출력할 때만 거꾸로 출력하든가, 맨 앞에서 부터 출력하든가 하면 됩니다.

---

처음에 배열은 [1,2,100,50,8] 와 같은 형태로 주어집니다.

따라서 처음에 string arr에 입력받아 v에 숫자만 parsing해 넣어줘야 합니다.

위의 코드는 그러한 작업을 하는 코드입니다.

---

이제 앞뒤를 체크해 줄것입니다. 

left가 true이고 right가 false이면 현재 앞 부분은 왼쪽이라는 의미입니다.

left가 false이고 right가 true이면 현재 앞 부분은 오른쪽이라는 의미입니다.

따라서 명령어 R을 만나면 left와 right의 상태를 바꿔주었습니다.ㅍ

마지막으로 left가 true이면 현재 왼쪽이 앞부분이므로 

앞에서 부터 출력해주면 됩니다.

반대로 right가 true이면 현재 오른쪽이 앞부분이르모 뒤에서 부터 출력해주면 됩니다.

---

전체 코드입니다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>
#include <tuple>
#define MAX 2100000000
#define inf LONG_MAX
#define big(a, b) a > b ? a : b
using namespace std;
using ll = long long;
using ull = unsigned long long;
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        string st;
        cin >> st;
        int n;
        cin >> n;
        string arr;
        cin >> arr;
        int a = 0;
        deque<int>v;
        bool check = false;
        for (int i = 0; i < arr.size(); i++) {
            if (arr[i] >= '0' && arr[i] <= '9') {
                if (arr[i + 1] >= '0' && arr[i + 1] <= '9' && !check) {
                    check = true;
                    a += arr[i] - '0';
                }
                else if (check) {
                    a *= 10;
                    a += arr[i] - '0';
                    check = false;
                    if (arr[i + 1] == '0') {
                        check = true;
                        continue;
                    }
                    v.push_back(a);
                    a = 0;
                }
                else {
                    v.push_back(arr[i] - '0');
                }
            }
        }
        bool left = true, right = false;
        for (int i = 0; i < st.size(); i++) {
            if (st[i] == 'R') {
                if (left)
                    right = true, left = false;
                else right = false, left = true;
            }
            else {
                if (v.empty()) {
                    cout << "error" << '\n';
                    check = true;
                    break;
                }
                if (left) v.pop_front();
                else v.pop_back();
            }
        }
        if (check)continue;
        cout << '[';
        if (left) {
            for (int i = 0; i < v.size(); i++) {
                cout << v[i];
                if (i == v.size() - 1)
                    break;
                cout << ',';
            }
        }
        else {
            for (int i = v.size() - 1; i >= 0; i--) {
                cout << v[i];
                if (i == 0)
                    break;
                cout << ',';
            }
        }
        cout << ']'<<'\n';
    }
 
    return 0;
}