[백준] 1874번: 스택 수열

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

1874번: 스택 수열

input으로 들어온 수열을 저장하는 큐(q), 그리고 스택(st)을 선언해서 사용했다.

 

숫자가 1~n까지 오름차순으로 증가하므로, for문으로 i=1~n까지 차례로 대입해준다.

for문이 돌 때마다 q.front()와 st.top()을 검사하는데,

여기서 q.front()는 현재 만들어야 하는 수열의 수를 담고 있다.

 

우리가 원하는 것은 q.front()와 st.top()이 같은 것이다.

st은 top으로 갈수록 숫자가 커지므로,

q.front()가 st.top()보다 작으면 st의 원소를 pop 해줘야 한다.

마찬가지로 q.front() == st.top()인 경우에도 입력된 수열을 만들기 위해 st를 pop 해준다. 다만 이때는 q의 원소도 함께 pop을 해주어야 한다(수열의 다음 숫자로 넘어가기 위해)

위의 내용을 while문을 통해 구현해주었다.

 

while문이 끝나면 i를 st에 push해준다.

 

for문이 끝나면 st의 원소를 하나씩 pop해가며 st.top()과 q.front()가 동일한지 검사해준다.

 

검사가 끝난 후 q가 비어있다면 입력된 수열을 모두 만들었다는 뜻이므로 result를 출력해준다.

q에 원소가 남아있다면 입력된 수열을 만들지 못한 것이므로 NO를 출력해준다.

(result는 push와 pop 연산을 +와 - 저장하는 큐로, st의 push와 pop 연산이 있을때마다 result에 +나 -를 push 해주면 된다)

 

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

int main() {
	int n;
	queue<int> q;
	stack<int> st;
	queue<char> result;

	cin >> n;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		q.push(a);
	}

	for (int i = 1; i <= n; i++) {
		while (!st.empty() && q.front() <= st.top()) {
			if (q.front() == st.top()) q.pop();
			st.pop();
			result.push('-');
		}

		st.push(i);
		result.push('+');
	}

	while (!st.empty() && q.front() <= st.top()) {
		if (q.front() == st.top()) q.pop();
		st.pop();
		result.push('-');
	}

	if (!q.empty()) {
		cout << "NO";
	}
	else {
		while (!result.empty()) {
			cout << result.front() << "\n";
			result.pop();
		}
	}
}