[ 백준 5430 ] AC (C++)

백준의 AC(5430) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 얼핏 문제만 보면 굉장히 단순한 문제이다. 'R'이 나올 때 마다 배열의 모든 원소들을 뒤집어주면 되고, 'D'가 나올 때마다

   첫 번째 원소를 계속해서 지워주면 된다.

   하지만 ! 정말로 배열을 하나 선언해놓고, 뒤집고 지우고를 하게되면 시간초과를 받게 된다.

   문제를 풀기 전에 먼저 왜 시간초과가 나는지 문제의 제약조건과 관련해서 알아보자.

   먼저 수행할 명령어들(R or D)가 최대 100,000개 까지 들어올 수 있다고 했다.

   또한, 배열의 갯수는 100,000 개이다. 그렇다면 명령어가 'R'로만 100,000개가 입력되었고, 배열이 100,000개가

   가득 차 있는 상태라고 생각해보자.

   'R'명령어대로 100,000개를 뒤집었다고 생각해보자. 뒤집기 위해서는 원소의 수 만큼인 100,000개를 하나하나 가리키면서

   뒤집어 주는 행위를 하게 될 것이다. 이걸 100,000번을 하면 ??

   100,000 x 100,000 번의 시간이 걸리게 될 것이고 이는 약 100억의 시간만큼 걸리게 될 것이고 문제의 제한시간인 1초내에

   당연히 실행될 수 없을 것이다.

   즉, 이 문제에서는 R이 들어올 경우 정말로 하나하나 배열을 뒤집으면 안되고 그것과 같은 효과를 내어야 한다.

  

2) 그렇다면 이제부터 본격적인 문제의 풀이에 대해서 알아보자.

   먼저 입력 부분에 대해서 알아보자. 입력부터가 상당히 마음에 안드는 형태로 주어진다.

   본인은 모두 char형 배열에 저장해주었는데, 명령어를 저장하는 것 까지는 그냥 주어지는 대로 저장하면 된다.

   꼭 char형 배열이 아닌, string을 사용해도 무방하다.

   문제는 숫자가 들어있는 배열을 입력받는 부분이다. 이 부분 또한 본인은 char형 배열을 사용해서 입력을 받았는데

   배열의 크기를 400,004 로 잡아주었다. 갑자기 이 무슨 뜬금없는 숫자일까 ??

   예를 들어서 { 1, 2, 3 } 을 입력받는다고 가정해보자. 우리가 입력받아야 할 것은 '[' , '1' , '2' , '3', ']', ','x2 개를 입력받아야

   한다. 즉, 우리는 3개의 숫자를 입력받는 다고 가정하면 숫자 3개 + '[' , ']' + , ','x2 개를 입력받아야 하는 것이고 총

   7개의 문자를 입력받아야 한다. 그럼 최대갯수인 100,000개를 입력받는 다고 생각해보자.

   아마 우리는 100,000개의 숫자 + '[', ']' (2개) + ','x99999 개를 입력받아야 할 것이다. 즉, 필요한 배열의 크기가

   100,001칸(숫자가 들어갈칸) + 99999칸(,이 들어갈 칸) + 2(괄호 2개가 들어갈 칸) 개가 된다. 

   그런데 ! 배열에 들어가는 숫자가 무조건 한자리가 아니다. 1 ~ 100 이므로, 최대 3자리 숫자가 100,000개 들어갈 수도 있는

   것이다. char형 배열로 입력 받을 경우, 한 자리씩 인식하기 때문에, 숫자가 들어갈 칸이 최대칸 x3 칸이 되어야 한다.

   예를 들어서 '100' 을 입력받게 되면, char형은 '1', '0', '0'을 따로 인식하기 때문에, 이 '1', '0', '0' 3칸이 들어갈 공간이 필요하다는

   것이다. 또한, 이 '1','0','0'을 '100'처럼 보이게 만드는 과정 또한 넣어주었다. 본인은 입력을 이런식으로 받아 보았다.

   또한, 이렇게 입력받은 것 중에서 괄호와 쉼표를 뺀 숫자들만 int형 배열에 새로 저장해 주었다.

3) 그렇다면 이제 본격적으로 'R' 연산과 'D'연산을 해보자.

   본인은 3가지 화살표(?)와, 현재 역순인지 아닌지 판단하는 변수, 총 4개의 변수를 사용해서 이 문제에 접근해 보았다.

   3가지 화살표는 배열의 가장 처음을 가리키는 Start_Idx와, 마지막을 가리키는 End_Idx, 그리고 현재점을 가리키는 Cur_Idx 이다.

   Start_Idx, End_Idx, Cur_Idx는 모두 int형 이다. 현재 순서를 가르키는 변수는 bool 형으로 true일때는 정방향을 false일때는 역방향

   을 의미하는 것 처럼 생각하고 풀었다. (bool Order)

   그렇다면 현재 배열에 { 1, 2, 3, 4 } 가 있다고 가정하고 설명해보겠다.

   현재 Start_Idx는 '0'(0번 Index가 시작점), End_Idx는 '3'(3번 Index가 마지막점), Cur_Idx = 0(현재는 0번 Index에 위치),

   Order = true(초기에는 정방향) 으로 설정된 상태이다.

   이 때, 'R'이 들어오게 되면 어떤 변화가 생기게 될까? 역순으로 바꾸었기 때문에 마치 배열이 { 4, 3, 2, 1 } 처럼 보이게 해야

   한다. 즉, Cur_Idx 를 End_Idx 값으로 바꾸어주고, Order 를 false로 바꾸어 주면 된다.

   지금까지 무슨말인지 잘 몰라도 좋다. 이 값들이 어떻게 계산되는지 한번 계속 보도록 하자.

   여기서 'D'가 들어왔다고 생각해보자. 그럼 첫 번째 원소를 없애야 하는데, { 4, 3, 2, 1 } 처럼 보이는 배열에서 첫 번째

   원소를 없애는 것이므로 { 3, 2, 1 } 이 되어야 한다. 이거는???

   End_Idx를 -- 시켜주고, Cur_Idx값도 End_Idx값으로 갱신해주면 된다.

   이 후, 다시 'R' 연산을 만나게 되면 ?? Cur_Idx를 다시 Start_Idx값으로만 바꿔주면 된다.

   위의 과정을 그림으로 한번 봐보자.

   { 1, 2, 3, 4 } 를 'R' 연산 후, 'D'연산 후, 'R' 연산을 하게 되었을 때 4가지 변수들이 어떻게 바뀌는지 그림으로 확인해보자.

  

     그림을 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순으로 보면 된다.

     왼쪽위의 그림은 가장 초기상태이다. 2번째 그림은 'R'연산을 했을 때의 화살표들의 결과이다.

     만약, 2번째 그림인 상태에서 정답을 출력해야 될 상황이라면, Cur_Idx부터 Start_Idx까지 순서대로 출력하면 답이 나오게 된다.

     3번째 그림은, 'D'연산을 했을 때이다. 배열에는 그 어떤 짓도 하지 않고, 단지 Cur_Idx와 End_Idx를 하나씩 앞으로 땡겨줄 뿐이

     다. 하지만, 그것이 의미하는 것은 "배열은 이제 여기까지 밖에 없어요 !" 라는 것을 의미한다.

     저 상태에서 다시 'R'연산을 했을 때(4번 그림), 다시 Cur_Idx가 Start_Idx로 가게 되며, 정답을 출력하게 되면

     Start_Idx부터 End_Idx까지만 출력을 해주면 된다.

     위와 같은 식으로 본인은 순서를 나타내는 변수 하나와, 3개의 화살표로만 구현을 한번 해보았다.

     설명이 많이 이해가 안될 수도 있고, 뭔가 본인도 설명하기 좀 힘들었던 문제였던 것 같은데 이해가 덜된 부분은 코드를

     보면서 이해해 보도록 하자.

     (그런데 글을 쓰고 나니까.. Cur_Idx는 필요가 없는 거 같다...)

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
#define MAX 100001
using namespace std;
 
int N, Start_Idx, End_Idx, Cur_Idx;
/* N = 배열의 크기
   Start_Idx = 배열의 시작점을 가르키는 화살표(초기값 = 0)
   Cur_Idx = 현재 내가 어디점을 가르키는지 저장하는 화살표(초기값 = 0)
   End_Idx = 배열의 마지막 점을 가르키는 화살표(초기값 = 배열의 크기 - 1)
 */
int Arr[MAX];     // 숫자만 추출해내서 저장하는 배열
bool Order;       // 현재 배열이 정방향인지 역방향인지 판단하기 위한 bool 형 변수
char P_Arr[MAX];  // 명령어(R , D)를 입력받고 저장하기 위한 char형 배열.
char Inp_Arr[MAX * 3 + 99999 + 2];    // 배열을 입력받을 때, '[', ']', ',' 까지
                                      // 모두 저장받기 위한 배열. (크기 주의)
 
template<typename T>
int My_Strlen(T *A)
{
    int i = 0;
    while (A[i] != 0) i++;
 
    return i;
}
 
void Initialize()
{
    for (int i = 0; i < MAX; i++)
    {
        P_Arr[i] = '\0';
        Arr[i] = 0;
    }
    for (int i = 0; i < MAX + 99999 + 2; i++)
    {
        Inp_Arr[i] = '\0';
    }
    Start_Idx = 0;
    Cur_Idx = 0;
    Order = true;
}
 
void Input()
{
    cin >> P_Arr;
    cin >> N;
    cin >> Inp_Arr;
    int Len = My_Strlen(Inp_Arr);
    int Idx = 0;
    /* 여기서 부터는 [ 부터 모든 숫자들과, ',' 그리고 ] 까지 모두 입력받는 부분입니다.*/
    for (int i = 0; i < Len; i++)
    {
        if (Inp_Arr[i] != '[' && Inp_Arr[i] != ']' && Inp_Arr[i] != ',')
        {
            int j = i;
            int x = 0;
            while (Inp_Arr[j] != '[' && Inp_Arr[j] != ']' && Inp_Arr[j] != ',')    
            {   
            /* 숫자가 한자리가 아닌 2자리 혹은 3자리 일 수도 있으므로, 
               2~3자리의 숫자들을 하나의 숫자로 만들어주기 위한 while문*/
                x = x + (Inp_Arr[j] - '0');
                x = x * 10;
                j++;
                i++;
            }
            x = x / 10;
            Arr[Idx++] = x;    // 숫자만 추출해내서 int형 배열에 따로 저장.
        }
    }
    End_Idx = Idx - 1;
}
 
void Solution()
{
    bool Flag = true;
    int Len = My_Strlen(P_Arr);
    int Size = My_Strlen(Arr);
 
    for (int i = 0; i < Len; i++)
    {
        if (P_Arr[i] == 'R')          // 입력된 명령어가 'R'일 경우
        {
            if (Order == true)        // 현재 배열이 정방향으로 되어있는 상황이라면
            {
                Order = false;        // 역방향으로 바꿔주고
                Cur_Idx = End_Idx;    // Cur_Idx의 값을 End_Idx로 변경.
            }
            else                      // 현재 배열이 역방향으로 되어있는 상황이라면
            {
                Order = true;         // 정방향으로 바꿔주고
                Cur_Idx = Start_Idx;  // Cur_Idx의 값을 Start_Idx로 변경.
            }
        }
        else                    // 입력된 명령어가 'D'일 경우
        {
            if (Size == 0)      // 크기가 0일 경우, 'D'연산이 들어오면 "error"출력.
            {
                Flag = false;   // Flag는 "error"를 출력했냐 안했냐를 판단해주는 변수로써
                                // "error"를 출력할 경우, 배열의 상태를 따로 출력하지 않아도 되므로
                                // 이 부분을 판단해 주기 위한 변수
                cout << "error" << endl;
            }
 
            if (Order == true)        
            {
         /* 현재 배열이 정방향일 경우 !
            배열에서 제일 앞에 값이 하나 사라진 것과 같은 효과를 내주어야 한다.
            즉, 배열의 시작점을 가르키는 Start_Idx의 값을 ++ 시킴으로써, 가장 앞에 값은 
            더 이상 배열에서 사용하지 않는 것처럼 보이게 하기 ! */
                Start_Idx++;
                Cur_Idx = Start_Idx;  // Cur_Idx값 또한 갱신
                Size--;               // 실제로 배열에서 값을 없애거나 공간을 해제한 것은 없지만 
                                      // Size는 감소한걸로 ! 
            }
            else
            {
        /* 현재 배열이 역방향일 경우 !
           실제로 배열을 뒤집은 것이 아니기 때문에, 배열에서 제일 마지막 값이 사라진 것과 같은
           효과를 내주어야 한다.
           즉, 배열의 마지막 점을 가르키는 End_Idx값을 --시킴으로써, 가장 마지막 값은
           더 이상 배열에서 사용하지 않는 것처럼 보이게 하기 ! */
                End_Idx--;
                Cur_Idx = End_Idx;   // Cur_Idx값 또한 갱신
                Size--;              // 얘도 실제 변화는 없지만 Size는 감소한 것처럼 보이기 ! 
            }
        }
    }
 
    // 정답을 출력해야 할 부분
    if (Flag == true)            
    {
        cout << "[";
        if (Order == true)    
        {
            // 현재 배열이 정방향이라면 출력의 범위는 ??
            // Start ~ End
            for (int i = Start_Idx; i <= End_Idx; i++)
            {
                if (i != End_Idx) cout << Arr[i] << ",";
                else cout << Arr[i];
            }
        }
        else
        {
            // 현재 배열이 역방향이라면 ??
            // End ~ Start
            for (int i = End_Idx; i >= Start_Idx; i--)
            {
                if (i != Start_Idx) cout << Arr[i] << ",";
                else cout << Arr[i];
            }
        }
        cout << "]" << endl;
    }
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}