[ SWEA 7534 ] 스택 장인 (C++)

SWExpertAcademy의 스택장인(7534 / D5) 문제이다.

[ 문제풀이 ]

스택을 이용해서, 주어진 수열을 출력할 수 있는지 문제에 주어진 예시들을 통해서 진행해보자.

먼저, 예제입력으로 주어진 첫 번째 TestCase를 이용해서 진행해보자.

[ 5 , 4 , 3 , 7 , 6 , 2 , 1 ]

먼저, 첫 번째 숫자까지 봤을 때, 스택으로 주어진 수열을 만드는 것이 불가능하다고 판단하는 경우가 있을까 ??

없다. 첫 번째 숫자는 반드시 출력을 할 수가 있다.

어떻게 ?? 해당 숫자까지 1부터 순차적으로 숫자를 넣어주면 된다.

가장 첫 번째 숫자가 '5'이므로, 1 부터 5 까지 스택에 push해보자.

[ 1 , 2 , 3 , 4 , 5 ] (편의상, 가장 오른쪽에 있는 숫자가 Stack의 가장 top() 이라고 생각하겠습니다.)

그럼, 1 부터 5까지 넣는 과정에서 '+++++' 가 추가될 것이다.

이 후, 5를 꺼내야 하기 때문에 결과적으로 스택의 상태와 대답의 상태를 출력해보면...

스택의 상태 : [ 1 , 2 , 3 , 4 ]

대답의 상태 : +++++-

두 번째로 출력해야 하는 숫자를 먼저 확인해보자. '4'이다. '4'는 현재 스택에 이미 삽입된 값이고, 스택의 top에 있는 값이다.

그대로 뽑아주면 된다.

스택의 상태 : [ 1 , 2 , 3 ]

대답의 상태 : +++++--

 세 번째로 출력해야 하는 숫자를 확인해보자. '3'이다. '3'은 현재 스택에 이미 삽입된 값이고, 스택의 top에 있는 값이다.

그대로 뽑아주면 된다.

스택의 상태 : [ 1 , 2 ]

대답의 상태 : +++++---

네 번째로 출력해야 하는 숫자를 확인해보자. '7'이다. '7'은 현재 스택에 아예 들어가 있지도 않은 숫자이다.

따라서, '7'을 뽑기 위해서, 먼저 '7'까지의 숫자들을 모두 stack에 삽입하는 과정을 진행해보자.

현재 '5'까지 숫자를 stack에 넣었기 때문에 그 다음에 들어갈 숫자는 '6'이고, 6 ~ 7 까지의 숫자들을 모두 stack에 삽입해 주면 된다.

스택의 상태 : [ 1 , 2 , 6 , 7 ]

대답의 상태 : +++++---++

이 상태에서, '7'을 뽑아주면 된다.

스택의 상태 : [ 1 , 2 , 6 ]

대답의 상태 : +++++---++-

다섯 번째로 출력해야 하는 숫자를 확인해보자. '6'이다. '6'은 현재 스택에 이미 삽입된 값이고 ,스택의 top에 있는 값이다.

그대로 뽑아주면 된다.

스택의 상태 : [ 1 , 2 ]

대답의 상태 : +++++---++--

나머지 숫자들인 '2'와 '1'도 각각의 상태에서 스택에 이미 삽입된 값이고, 스택의 top에 있는 값들이므로 순차적으로 뽑아주면 된다.

최종정답 : +++++---++----

이렇게 해서 첫 번째 TestCase는 대답이 가능한 케이스라는 것을 확인할 수 있다.

그러면, 이제는 3번째 TestCase로 넘어가볼 것인데, 그 전에 우리가 위의 과정에서 "현재 숫자를 출력하기 전에 고려 및 진행 했던 부분들"에 대해서 부터 정리를 해보자.

가장 첫번째로, "현재 출력해야 하는 숫자가, 스택에 이미 삽입된 값인지 아닌지를 판단" 해 주었다.

두 번째로, "스택에 삽입되지 않은 값"에 대해서는, 해당 값 까지 스택에 삽입하는 과정을 진행해 주었다.

반대로 "스택에 삽입되어 있는 값"에 대해서는, "스택의 top에 있는 값인지를 판단"해 주었다.

물론, 위의 케이스에서는 "이미 스택에 삽입되어 있는 모든 경우에서, 모두 스택의 top()에 있는 경우만 존재" 했었다.

따라서, 이게 아닌 경우를 알아보기 위해서 TestCase3을 진행해보자.

1. 현재 출력해야 하는 숫자가, 스택에 이미 삽입된 값인지 아닌지를 판단한다.

2. 아직 스택에 삽입된 적이 없는 값이라면, 해당 값 까지 스택에 삽입하는 과정을 진행한다.

3. 이미 스택에 삽입된 값이라면, 해당 값이 스택의 top에 있는 값인지 확인하고 출력한다.

TestCase3 : [ 2 , 4 , 5 , 1 , 3 ]

1. 첫번째 숫자 = 2

'2'는 아직 스택에 삽입된 적이 없는 값이다. 따라서 2까지 스택에 삽입하는 과정을 진행해보자.

스택의 상태 : [ 1 , 2 ]

대답의 상태 : ++

이 후, 2를 뽑아주면 된다.

스택의 상태 : [ 1 ]

대답의 상태 : ++-

2. 두 번째 숫자 = 4

'4'는 아직 스택에 삽입된 적이 없는 값이다. 따라서 4까지 스택에 삽입하는 과정을 진행해보자.

첫 번째 숫자를 삽입하는 과정에서 '2'까지 삽입을 했으므로, 그 다음 숫자는 3이고 3 ~ 4에 있는 숫자들을 순차적으로 삽입해주면 된다.

스택의 상태 : [ 1 , 3 , 4 ]

대답의 상태 : ++-++

이 후, 4를 뽑아주면 된다.

스택의 상태 : [ 1 , 3 ]

대답의 상태 : ++-++-

3. 세 번째 숫자 = 5

'5'는 아직 스택에 삽입된 적이 없는 값이다. 따라서 5까지 스택에 삽입하는 과정을 진행해보자.

두 번째 숫자인 '4'를 삽입하는 과정에서 '4'까지 삽입을 했으므로, 그 다음 숫자를 5이고 5 ~ 5에 있는 숫자들을 순차적으로 삽입해 주면 된다.

스택의 상태 : [ 1 , 3 , 5 ]

대답의 상태 : ++-++-+

이 후, 5를 뽑아주면 된다.

스택의 상태 : [ 1 , 3 ]

대답의 상태 : ++-++-+-

4. 네 번째 숫자 = 1

'1'은 이미 스택에 삽입된 적이 있는 값이다. 그런데, 현재 스택의 top값은 '3'이다. 즉, 현재 뽑고자 하는 숫자인 '1'이 아니라는 것이다. 이 경우에는 어떻게 진행해 주어야할까 ??

이 경우, 절대로 정답을 만들 수 없게 된다. 왜 ?? 1을 뽑기 위해서 pop() 연산을 2번 진행했다고 가정해보자.

그렇게 되면, 우리가 만들고자 하는 수열은 [ 2 , 4 , 5 , 1 , 3 ] 인데, 이게, [ 2 , 4 , 5 , 3 , 1 ] 이 되버리기 때문이다.

따라서, 이 경우에는 정답이 될 수가 없다.

정리를 해보자.

1. 현재 숫자가 스택에 삽입되어 있는 값인지 아닌지 판단한다.

2. 현재 숫자가 아직 스택에 삽입되지 않았다면, 해당 숫자까지 스택에 삽입해준다.

3. 현재 숫자가 이미 스택에 삽입되어 있다면, 현재 숫자가 스택의 top에 있는 값인지 확인해준다.

4. 만약, 현재 숫자가 스택의 top에 있는 값이 아니라면, 이 경우에는 정답이 불가능한 경우이다.

본인은 이를 코드로 구현할 때, 실제로 Stack을 사용해 주었고, Insert[]라는 1차원 bool형 배열을 이용해서 삽입의 여부를 판단해 주었다.

Insert[A] = true의 의미는 "A라는 숫자는 이미 스택에 삽입되어 있습니다." 를 의미하고, 반대로 false라면, "A라는 숫자는 아직 스택에 삽입된 적이 없습니다." 를 의미한다.

그리고 소스코드로 위의 과정을 그대로 구현해 주었다.

[ 소스코드 ]

#include <iostream>
#include <cstring>
#include <stack>
#include <vector>
 
#define endl "\n"
#define MAX 100010
using namespace std;
 
int N;
int Arr[MAX];
bool Insert[MAX];
stack<int> Stack;
vector<char> Answer;
 
void Initialize()
{
    while (Stack.empty() == 0) Stack.pop();
    Answer.clear();
    memset(Insert, false, sizeof(Insert));
}
 
void Input()
{
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        cin >> Arr[i];
    }
}
 
void Solution()
{
    int Num = 1;
    while (Num != Arr[1])
    {
        Stack.push(Num);
        Answer.push_back('+');
        Insert[Num++] = true;
    }
    Stack.push(Num);
    Answer.push_back('+');
    Insert[Num++] = true;
    
    for (int i = 1; i <= N; i++)
    {
        int Find_Num = Arr[i];
        if (Insert[Find_Num] == true)
        {
            if (Stack.top() == Find_Num)
            {
                Answer.push_back('-');
                Stack.pop();
            }
            else
            {
                Answer.clear();
                Answer.push_back('N');
                Answer.push_back('O');
                return;
            }
        }
        else
        {
            while (Num != Arr[i])
            {
                Stack.push(Num);
                Answer.push_back('+');
                Insert[Num++] = true;
            }
            Stack.push(Num);
            Answer.push_back('+');
            Insert[Num++] = true;
 
            Stack.pop();
            Answer.push_back('-');
        }
    }
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " ";
        for (int i = 0; i < Answer.size(); i++) cout << Answer[i];
        cout << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}