C++ / 백준 / 1874 / 스택 수열

문제

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

1874번: 스택 수열

문제풀이

들어온 입력을 스택을 이용해서 pop을 했을 때 순서대로 만들 수 있는지 여부를 출력하는 문제이다.

처음엔 오름차순 순열을 따로 만들어 지저분하게 풀었는데 다른 사람의 코드를 참고하여 다시 풀었다.

	for (idx = 0; idx < n; ++idx) {
		while (s.empty() || s.top() != input[idx]) {
			if (num >= n) break;
			s.push(++num);
			answer.push_back('+');
		}
		if (s.top() == input[idx]) {
			s.pop();
			answer.push_back('-');
		}
		else {
			cout << "NO";
			return 0;
		}
	}

스택이 비어있거나 스택의 top부분이 현재 찾아야 하는 값과 다를 경우, 

스택 s에 집어넣는 num값이 n미만 일 때, 스택에 num+1을 하여 push 하고 answer에도 '+'을 push 한다.

while문을 벗어나는 경우는 num >= n 또는 s.top() == input[idx] 일 때이다.

num이 n이상이어서 while문을 벗어난 경우에는 더 이상 push를 할 수 없다.

이 경우 pop만 해야 되는데 s.top이 input[idx]가 아닌 경우 수열을 만들 수 없으므로 NO를 출력하고 종료,

아닌 경우 pop()을 하고 answer에 '-'을 push 한다.

 

코드

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

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

	int n(0), idx(0);
	cin >> n;

	vector<char>answer;
	vector<int>input(n, 0);
	stack<int>s;

	int num(0);

	for (idx = 0; idx < n; ++idx)
		cin >> input[idx];

	for (idx = 0; idx < n; ++idx) {
		while (s.empty() || s.top() != input[idx]) {
			if (num >= n) break;
			s.push(++num);
			answer.push_back('+');
		}
		if (s.top() == input[idx]) {
			s.pop();
			answer.push_back('-');
		}
		else {
			cout << "NO";
			return 0;
		}
	}

	for (idx = 0; idx < answer.size(); ++idx)
		cout << answer[idx] << '\n';
}