백준 5430번 AC _ 덱(DEQUE) (c++)

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

5430번: AC

이 문제는 난이도 무려 19%에 달하는 나름 백준에 고난이도로 분류되는 문제이지만, 실제 구현 난이도는 그리 높지 않다.
우선 이 문제가 덱, DEQUE 문제로 분류된 이유는 단순히 배열의 앞에 있는 원소를 pop하기 때문이다.
하지만 이 문제는 좋아, 그럼 배열을 뒤집고, 앞의 원소를 pop하는 함수를 만들면 되겠군! 하면서 접근하면 바로 함정에 빠지게 되는 것이다.
애초에 난이도 19%에서 한번 의심을 해주고, 시간초과가 1초임에 의심을 해줄 필요가 있다.

배열에서  1 2 3 4 5 6 7 8 9 10을 거꾸로 프린트 하라고 하면 어떻게 할 것인가?
새로운 배열에 거꾸로 저장한 뒤에 프린트 할 것인가?
아니다! 그냥 뒤부터 프린트하면 되는 것이다. 그럼 애초에 재배열 자체가 필요없다.

그럼 두번째, 그럼 어떻게 pop할 것인가?
그냥 pop을 하면 앞에 원소가 빠지고, 뒤집은 채 pop하면 뒤에 원소가 빠진다.
하지만 단순하게 생각하면 결국 양 끝쪽에서만 빠진다는 소리다.
원래 순서일때 pop된 숫자를 세고, 뒤집어졌을 때 pop된 숫자를 센 뒤 결국 마지막에 양 쪽에서 그만큼 pop을 시켜주고 Reverse 명령의 수만 보면 된다.

추가적으로 C++ 로 구현하는 사람들은 input배열을 어떻게 처리해서 int형 배열로 변환시킬 지도 하나의 과제였을 것이다.
나는 ,를 기준으로 하나하나 문자로 읽은 뒤 stoi로 변환시켜주는 방법을 사용하였다.
코드를 보면 다음과 같다.

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

string str; // RDD 문자
int arr_size; // 배열 사이즈
string str_arr; // 배열 문자로 읽기

int* StoiArr(string str){
    int* arr = new int[arr_size]; // 배열 사이즈 기준으로 배열 동적할당
    int str_len = str.length(); 
    string temp_str = "";
    int count = 0;
    for (int i=1; i<str_len; i++){
        if (str_arr[i] == ']') {
            if (temp_str != "") arr[count] = stoi(temp_str);
            break;
        }
        else if (str_arr[i] == ','){
            arr[count] = stoi(temp_str);
            count+=1;
            temp_str="";
        }
        else temp_str += str_arr[i];
    }
    return arr;
}

int main(void){
    int n;
    cin>>n;
    for (int z=0; z<n; z++){
        cin>>str; 
        int len = str.length(); // 문자길이
        cin >> arr_size;
        cin >> str_arr;
        int* arr = StoiArr(str_arr); // input 배열 숫자 배열로 리턴하는 함수.

        int R_count = 0; // Reverse 몇번이었나?
        int start_D = 0; // 앞에서 D 몇번이었나?
        int end_D =0;    // 뒤에서 D 몇번이었나?
        bool error = 0;
        for (int i=0; i<len; i++){
            if (str[i] == 'R') R_count +=1;
            else if (str[i] == 'D') {
                if (arr_size-(start_D+end_D) == 0){
                    cout << "error" << '\n';
                    error = 1;
                    break;
                }
                if (R_count%2==0) start_D+=1;
                else end_D+=1;
            }
        }
        if (!error){
            if (arr_size-(start_D+end_D) == 0){
                cout << "[]" << '\n';
            }
            else if (R_count%2==0){
                cout << "[";
                for (int i=start_D; i<(arr_size-end_D-1); i++){
                    cout << arr[i] << ",";
                }
                cout << arr[arr_size-end_D-1] << "]" <<"\n";
            }
            else{
                cout << "[";
                for (int i=(arr_size-end_D-1); i>=start_D+1; i--){
                    cout << arr[i] << ",";
                }
                cout << arr[start_D] << "]" <<"\n";
            }
        }
        delete []arr;
    }
    return 0;
}

 

끝.