1874번: 스택 수열

메모리

시간

1596 KB

28 ms

Code

#include <stack>
#include <cstdio>

using namespace std;

int main()
{
	stack<int> stack;
	int n;
	scanf("%d", &n);

	int arr[n + 1];
	char count[n + 1];

	for (int i = 1; i < n + 1; i++)
		scanf("%d", &arr[i]);
	int j = 1;
	int m = 0;
	for (int i = 1; i < n + 1; i++)
	{
		if (stack.empty())
		{
			stack.push(j);
			count[m++] = '+';
			j++;
		}
		while (arr[i] != stack.top() && j < n + 1 && j > stack.top())
		{
			stack.push(j);
			count[m++] = '+';
			j++;
		}
		if (arr[i] == stack.top())
		{
			stack.pop();
			count[m++] = '-';
		}
		else
		{
			printf("NO");
			return 0;
		}
	}
	count[m] = '\\0';
	for (int i = 0; i < m; i++)
		printf("%c\\n", count[i]);
	
	return 0;
}

문제 풀이

주어진 수열을 stack을 사용하여 만드는 문제이다.

스택에는 오름차순으로만 수를 넣을 수 있는데 수열을 만들지 못할 시에 no를 출력한다.

수열과 일치 할때까지 정수를 push 하다 일치하는 값을 넣으면 pop을 해주는 기본 방식으로 풀이하였다.

push 나 pop 의 조건에 걸리지 않으면 no 출력 종료.