[백준 1874] 스택 수열 [C]

백준 - 1874

---

풀이

다음과 같은 규칙이 존재한다.

• 둘째 줄부터 입력받은 수까지 push를 해주어야 하며, push는 이전에 입력된 수보다 큰 수가 입력될 때만 발생한다.
• push가 발생하거나, 이전에 입력된 수보다 작은 수가 입력될 경우 불필요해 생략한 후 pop가 발생해야한다.
• 만약, pop이 발생하지 않았다면, 스택을 이용해 수열을 만들 수 없다는 의미이다.

따라서, 둘째 줄부터 입력받는 n개의 수들을 저장할 필요가 없다.

---

소스코드

#include <stdio.h>
int main(){
    int n;
    scanf("%d", &n);
    int stack[n], top = 0, val, idx = 0, num = 0;
    char op[2*n];
    for (int i = 0; i < n; i++){
        scanf("%d", &val);
		
        for (int j = num; j < val; j++){
            stack[top++] = ++num;
            op[idx++] = '+';
        }
        if (stack[top-1] == val){
            top--;
            op[idx++] = '-';
        }else {
            idx = 0;
            puts("NO");
            break;
        }
    }
    if (idx)
        for (int i = 0; i < 2*n; i++)
            printf("%c\n", op[i]);
}

---

출처

1874번: 스택 수열