#1874. 스택수열

#1874. 스택수열

1. 문제 이해

 우선, 제목에서 보이듯이 스택을 사용하여 해결하는 문제인걸로 보입니다. test case로 입력을 '4 3 6 8 7 5 2 1'을 받았을때, 이 수열을 1부터 n까지 오름차순으로 들어오는 수로 만든 stack으로 만들 수 있다면 push, pop 과정을 나열하거나, 수열이 만들어 지지 않는 다면 NO를 출력하는 문제입니다.

2. 접근방법

 저는 1단계와 2단계로 나누어서 진행을 해보았습니다.

1단계, no 단계를 생각하지 않고, 어떻게 push(+)와 pop(-)을 출력해 나갈지에 대한 루틴 고민하기.

2단계, NO로 가는 경로 찾기.

3. 문제 해결

[1단계]

 test case : [4 3 6 8 7 5 2 1]를 이용하여 루틴을 찾아 보도록 하겠습니다.

맨 처음으로 4를 입력 받게 된다면, 우리는 1부터 4까지 push를 할 수 밖에 없습니다. 즉, 입력받는 새로운 값이 증가할때 마다 결국엔 push할 수 밖에 없다는 것 입니다.

 자, 여기서 힌트를 얻어 MAX라는 기준을 만들어 새로 입력받는 값이 MAX보다 크다면, 이전 MAX부터 다음 MAX만큼 push가 일어나는 루틴을 찾을 수 있습니다.

 반대로, MAX보다 작다면 현재 스택에 top의 위치를 확인합니다. 스택에 경우, top이 가리키는 값이 pop 될 수 밖에 없기 때문에 top이 가리키는 값이 test case 다음값과 같다면 pop을 수행해 줍니다.

[2단계]

 

 이제 NO의 경우를 찾아 보도록 하겠습니다. 이 문제의 경우에는 1단계에서 조금만 더 생각해 본다면 쉽게 solution을 찾을 수 있습니다. 

 MAX보다 작다면 현재 top의 위치를 확인하여 그 값이 test case 다음값과 같다면 pop을 수행했습니다. 이 부분을 상기 한다면, 반대로 test case 값과 같지 않을때는 NO가 나오는것을 생각해 낼 수 있습니다.

#include <stdio.h>
#define MAX 100000
#define S_MAX 200000
 
typedef struct Stack {
    int s[S_MAX];
    int top;
}Stack;
 
Stack stack;
 
int main() {
    int num;
    int input[MAX];
    char output[S_MAX];
    int i, j;
    stack.top = -1;
    int cnt = 0;
    int output_i = 0;
    int max = 0;
 
    scanf("%d", &num);
 
    for (i = 0; i < num; i++) {
        scanf("%d", &input[i]);
        if (max < input[i]) {
            for (j = max; j < input[i]; j++) {
                max = input[i];
                
                stack.s[++stack.top] = (++cnt);
                output[output_i++] = '+';
            }
            --stack.top;
            output[output_i++] = '-';
        }
        else if (max > input[i]) {
            if (stack.s[stack.top] != input[i]) {
                printf("NO");
                return;
            }
            else if (stack.s[stack.top] == input[i]) {
                --stack.top;
                output[output_i++] = '-';
            }
        }
    }
    for (i = 0; i < output_i; i++) {
        printf("%c\n", output[i]);
    }
}

※ 느낀점 

1. 기능(function)에 printf는 절대 넣지 말자.

2. 문자열을 출력 하는 방법 2가지.

  - %s : 'n\'(null)을 만날때까지 출력. 

  - %c : for문 사용 (여기선 null이 없기 때문에)

3. 출력은 입력의 2배가 된다. (이 문제의 경우에서만!)