BOJ [1874] 스택 수열

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

스택 문제에서 조금 더 꼬아본 문제.

풀 때는 오래걸렸는데 스택의 기본 개념을 고려하면 쉽게 풀 수 있던 문제였다.

불가능한 경우는 입력값(pop했을 때의 값)이 stack[top]과 다른 경우가 되겠다.

push와 pop이 각 n번씩 수행되고 n번 입력하므로 O(3n) = O(n)으로 풀 수 있다.

stack용 배열 하나와 예제 출력에 불가능한 경우 NO, 가능한 경우에만 +, -로 표현하도록 되어 있으니 출력용 배열을 하나 더 만들었다.

#include <cstdio>

int stack[100000] = { 0 };
char out[200000] = { 0 };

int main()
{
	int n, in = 0, stTop = 0, outTop = 0;
    // in = 스택에 삽입할 자연수(1부터 차례대로)
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		int num;
		scanf("%d", &num);

        // 받는 값은 n값 이상이 될 수 없다.
		if (num > n)
		{
			printf("NO\n");
			return 0;
		}

        // 스택에 삽입할 자연수가 num보다 낮으면 push
        // push는 최대 n번까지 수행한다.
		if (in < num)
		{
			for (int j = in; j < num; j++)
			{
				stack[stTop++] = ++in;
				out[outTop++] = '+';
			}
		}

        // 스택에 num값과 같을 때까지 자연수를 삽입하면 pop을 수행한다.
		if (num == stack[stTop - 1])
		{
			stack[--stTop] = 0;
			out[outTop++] = '-';
		}
        // num값과 stack[stTop]이 다르면 잘못된 경우이다.
		else
		{
			printf("NO\n");
			return 0;
		}
	}

    // 저장했던 +, -를 전부 출력한다.
	for (int i = 0; i < outTop; i++)
		printf("%c\n", out[i]);

	return 0;
}