백준 1874 스택 수열 [C]

문제

https://www.acmicpc.net/problem/1874

1874번: 스택 수열

 

 

풀이

4, 3, 6, 8, 7, 2, 5, 1 과 같은 스택 수열이 있다고 가정해보자.

맨 처음 숫자 4를 만들기 위해서는 [1,2,3,4]를 차례대로 스택에 PUSH해야한다.

S = [1,2,3,4] 

그리고 나서 4,3은 차례대로 POP을 하여 스택 수열을 만족시킬 수 있다.

그렇다면, 그 다음 숫자인 6을 만들기 위해서는 [5,6]을 차례대로 스택에 PUSH 해야한다.

S = [1,2,5,6]

그리고나서 6은 POP을 하여 스택 수열을 만족 시킬 수 있다.

그 다음 숫자인 8을 만들기 위해서는 [7,8]을 차례대로 스택에 PUSH 해야한다.

[1,2,5,7,8]

그리고 나서 스택에 있는 수들을 모두 POP을 해주면 우리가 원하는 스택 수열을 만들 수가 있다.

 

스택에 PUSH하는 순서가 반드시 오름차순 이므로 현재 스택에 PUSH 해야 하는 숫자(아래 코드에서의 cnt)를 지정해놓고 풀이해주면 쉽게 풀이 할 수 있다.

 

코드

#include<stdio.h>
#include<stack>

#define LEN 200000

using namespace std;

int set[LEN], N, cnt = 1, len = 0;
char ans[LEN];
stack<int> S;

int main() {
    int i;
    scanf("%d", &N);
    for (i = 0; i < N; i++) {
        scanf("%d", &set[i]);
    }
    cnt = 1;
    for (i = 0; i < N; i++) {
        if (S.empty() || S.top() < set[i]) {
            for (cnt = cnt; cnt <= set[i]; cnt++) {
                ans[len++] = '+';
                S.push(cnt);
            }
            ans[len++] = '-';
            S.pop();
        } else if (S.top() == set[i]) {
            S.pop();
            ans[len++] = '-';
        } else {
            break;
        }
    }
    if (i != N) {
        printf("NO");
        return 0;
    }
    for (i = 0; i < len; i++) {
        printf("%c\n", ans[i]);
    }
    return 0;
}