백준 1874 - 스택 수열

스택을 활용해 해결할 수 있는 문제입니다.

초반에 문제를 이해하는데 생각보다 시간이 걸렸던 문제입니다. stack의 LIFO(Last In First Out) 특성을 이용해 push와 pop을 통해 입력된 수열을 만들 수 있다면 push와 pop의 순서를 출력하고 안된다면 NO를 출력하는 문제입니다.

#include <iostream>
#include <vector>
#include <stack>

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);

	int n;
	std::cin >> n;

	std::stack<int> current;
	std::vector<int> input;
	int curInput = 0;
	int curNum = 1;

	std::vector<char> output;

	for (int i = 0; i < n; i++)
	{
		int tmp;
		std::cin >> tmp;
		input.push_back(tmp);
	}

	while (curInput != n)
	{
		int top = current.size() == 0 ? 0 : current.top();
		int target = input[curInput];

		if (top < target)
		{
			current.push(curNum++);
			output.push_back('+');
		}
		else if (top == target)
		{
			current.pop();
			curInput++;
			output.push_back('-');
		}
		else
		{
			std::cout << "NO\n";
			return 0;
		}
	}

	for (int i = 0; i < output.size(); i++)
	{
		std::cout << output[i] << "\n";
	}

	return 0;
}

해당 코드의 Time complexity는 O(N)처럼 보일 수 있으나, while문이 몇번 돌지 장담할 수 없기에 O(N)이 아닐 수 있습니다.