[Baekjoon] 1874번: 스택 수열

 

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

1874번: 스택 수열

 

---

 

문제 해결 과정

착안

수열을 만들 수 있는지 확인하는 별다른 방법이 떠오르지는 않아, 문제에서 제시한 과정을 그대로 구현하여 문제를 해결하고자 하였다. 구체적으로는 아래와 같이 구현하고자 했다.

 

• 스택이 비어있거나 Top에 위치한 요소가 현재 수열의 항보다 작으면 push를 반복
• (위 반복이 끝난 후) 스택의 Top에 위치한 요소가 현재 수열의 항과 같으면 pop 수행, 같지 않으면 중단

 

구현

위의 과정은 수를 입력받을 때마다 실행할 수 있는 과정이므로 이 점에 중점을 두어 구현하였다. 정확하게 스택에서 push 또는 pop을 실행하는 횟수는 알 수 없기 때문에 std::vector<> 클래스를 활용하여 저장하였다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

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

using namespace std;

vector<char> Op;
stack<int> S;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int N, n = 1;
	cin >> N;
	
	for (int i = 0; i < N; i++)
	{
		int num;
		cin >> num;

		while (S.empty() || S.top() < num)
		{
			Op.push_back('+');
			S.push(n++);
		}

		if (S.top() == num)
		{
			Op.push_back('-');
			S.pop();
		}
		else
		{
			cout << "NO\n";
			return 0;
		}
	}

	for (char c : Op)
		cout << c << "\n";

	return 0;
}

 

실행 결과