[백준 1874] 스택 수열 (C++)

풀이

문제부터 이해해보자.

 

핵심은 스택을 이용해서 원하는 숫자를 만들 수 있는지? 아닌지이다.

input

8 4 3 6 8 7 5 2 1

output

+ + + + - - + + - + + - - - - -

하나씩 차근차근 진행해보면,

 

4를 만들기 위해서는 push 4번, pop 1번

+ + + + Stack [1, 2, 3, 4]

+ + + + - Stack [1, 2, 3]

 

3을 만들기 위해서는 pop 1번

+ + + + - - Stack [1, 2]

 

6을 만들기 위해서는 push 2번, pop 1번

+ + + + - - + + Stack [1, 2, 5, 6]

+ + + + - - + + - Stack [1, 2, 5]

 

8을 만들기 위해서는 push 2번, pop 1번

+ + + + - - + + - + + Stack [1, 2, 5, 7, 8]

+ + + + - - + + - + + - Stack [1, 2, 5, 7]

 

7을 만들기 위해서는 pop 1번

+ + + + - - + + - + + - - Stack [1, 2, 5]

 

5, 2, 1을 각 각 pop 1번씩만 해주면 해결할 수 있다.

따라서 결과는

+ + + + - - + + - + + - - - - -

 

구현은

queue에 현재 만들고자 하는 숫자들을 넣어주고,

현재 만들려고 하는 숫자를 stack의 top과 비교하면서 만들 수 있다면 push 하면서 +를 채워나가고

만들지 못한다면 No를 출력하면 된다.

여기서 만들지 못한다는 것은 현재 queue의 front 값과 stack의 top 부분에서

queue.front() < stack.top() 이면 만들지 못하는 것이다.

 

ret이라는 벡터는 출력을 위한 +, -를 저장하는 공간이다.

#include <iostream>
#include <stack>
#include <queue>
using namespace std;

int n;
stack<int> st;
queue<int> q;
vector<char> ret;
// stack에 push하는 순서는 반드시 오름차순
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int x;
		cin >> x;
		q.push(x);
	}

	int num = 1;
	bool ok = true;
	while (!q.empty())
	{
		int now = q.front();

		if (!st.empty() && st.top() > now)
		{
			ok = false;
			break;
		}
		if (st.empty())
		{
			st.push(num++);
			ret.push_back('+');
		}
		else
		{
			if (st.top() == now)
			{
				st.pop();
				ret.push_back('-');
				q.pop();
			}
			else
			{
				st.push(num++);
				ret.push_back('+');
			}
		}
	}

	if (ok)
	{
		for (int i = 0; i < ret.size(); i++)
			cout << ret[i] << '\n';
	}
	else
		cout << "NO\n";

	return 0;
}