[BOJ] 5430 AC

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

5430번: AC

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

deque(덱)

 

---------------------------------------------------풀이----------------------------------------------------

 

linked list를 사용하면 바로 구현이 가능할 것 같은데, stl을 사용하면 구현할 필요도 없을 것 같아서 deque을 사용하였다.

vector와 다른 점은 random access가 가능한 점은 여전하지만, 맨 앞과 맨 뒤 삭제가 매우 빠르다는 점이다.

mode를 설정해 앞에서부터 볼 때는 0, 뒤에서부터 볼 때는 1로 설정했다.

즉, mode가 0이면 앞에서부터가 정방향, 1이면 뒤에서부터가 정방향으로

'D' 명령이 들어올 경우 각각 pop_front()와 pop_back()을 사용하였다.

'R' 명령이 들어오면 mode XOR 1을 통해 mode를 바꿔주었다.

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stack>
#include <limits.h>
#include <deque>

using namespace std;

// 배열에 들어있는 수의 개수
int N;
// 배열
deque<int> arr;

string in = "";
// 0이면 앞에서부터, 1이면 뒤에서부터
int mode = 0;

void init_all(){
    in = "";
    arr.clear();
    mode = 0;
}

// string을 arr에 숫자로 바꿔서 저장
void make_arr(){
    int idx = 1;
    int num = 0;
    while(in[idx] != ']'){
        if(in[idx] == ','){
            arr.push_back(num);
            num = 0;
        }
        else{
            num = num * 10 + in[idx]-'0';
        }
        idx++;
    }
    if(N > 0) arr.push_back(num);
}

int main(void){
    FASTIO;
    int T;
    cin >> T;
    for(int t = 0; t < T; t++){
        init_all();
        // 수행할 함수
        string p;
        cin >> p;
        cin >> N;
        // 정수 배열 입력받기
        cin >> in;
        make_arr();
        bool err_flag = false;
        for(int i = 0; i < p.length() && !err_flag; i++){
            switch(p[i]){
                // 뒤집기 -> 수의 순서 뒤집기
                case 'R':
                    mode ^= 1;
                break;
                // 버리기 -> 첫 번째 수 버리기
                case 'D':
                    if(arr.empty()){
                        err_flag = true;
                        break;
                    }
                    // 앞의 수 버리기
                    if(mode == 0){
                        arr.pop_front();
                    }
                    // 뒤의 수 버리기
                    else{
                        arr.pop_back();
                    }
                break;
            }
        }
        if(err_flag){
            cout << "error\n";
        }
        else{
            // 앞에서부터 출력
            if(!mode){
                cout << "[";
                for(int i = 0; i < arr.size(); i++){
                    cout << arr[i];
                    if(i < arr.size()-1){
                        cout << ",";
                    }
                }
                cout << "]\n";
            }
            // 뒤에서부터 출력
            else{
                cout << "[";
                for(int i = arr.size()-1; i >= 0; i--){
                    cout << arr[i];
                    if(i > 0){
                        cout << ",";
                    }
                }
                cout << "]\n";
            }
        }
    }

    return 0;
}

 

 

---------------------------------------------------후기----------------------------------------------------

 

출력 형식때문에 계속 틀린 문제...

마지막에 [~~~]\n로 출력해야 하는데 \n을 빼먹어서 계속 16%에서 틀렸었다.....