[백준] #1874

문제입니다
n까지의 수를 스택에 넣었다가 뽑으면서 push와 pop을 이용한 수열이 가능한지 불가능한지 확인하고 가능하면 push는 + pop은 - 를 출력하는 문제입니다

예시를 들면 첫번째 줄에 8를 입력하면 1 2 3 4 5 6 7 8 즉 1부터 8까지의 수가 stack에 push가 되야하고 그 밑줄에 예시로

4 3 6 8 7 5 2 1

이란 수열을 준다면

push() -> push() -> push() -> push() -> pop() -> pop() -> push() -> push() -> pop() -> push() -> push() -> pop() -> pop() -> pop() -> pop() -> pop()
= + + + + - - + + - + + - - - - -

과 같은 결과가 나와야 합니다
또 다른 예시로 5를 입력한 후

1 2 5 3 4

라는 수열을 준다면

push() -> pop() -> push() -> pop() -> push() -> push() -> push() -> pop() -> pop() -> ...

위와 같이 1 2 5 3까지는 나올 수 있어도 4는 3전에 pop()이 되었기 때문에 결과적으로는 불가능하기에 NO를 출력합니다

다음은 코드입니다

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

using namespace std;

int main() {
	int n;
	int tmp = 1;
	int example[100000];
	// 숫자 값 저장하는 stack
	stack<int> s1;	
	// 문자 값 저장하는 vector
	vector<char> answer;

	cin >> n;

	for (int i = 0; i < n; i++) {
		int num; cin >> num;
		// 숫자 스택이 비어있지 않고 스택의 제일 위의 값이 입력받은 num값이라면 pop하고 벡터에 - push
		if (!s1.empty() && s1.top() == num) {
			s1.pop();
			answer.push_back('-');
		}
		// tmp가 num보다 작거나 같을 때 num까지 push하고 +도 push후 제일 위의 값 pop 후 - push
		else if (tmp <= num) {
			while (tmp <= num) {
				s1.push(tmp++);
				answer.push_back('+');
			}
			s1.pop();
			answer.push_back('-');
		}
		// 스택의 제일 위의 값보다 num이 작다면 no 출력
		else if (!s1.empty() && s1.top() > num) {
			cout << "NO";
			return 0;
		}
	}
	for (auto x : answer)
		cout << x << "\n";
	return 0;
}

숫자 값을 저장하는 stack과 출력할 문자 값을 저장하는 vector을 만들어 준 후 n을 받을 입력값을 받은 후 for문을 돌면서 값을 하나씩 받고 그 숫자까지 tmp를 이용해서 push를 계속 해주고 answer에 +값 추가하고 그 숫자라면 pop과 answer에 -추가를 진행하면서 스택의 제일 위의 값이 입력받은 값이라면 pop과 -를 실행합니다. 그리고 두번째 예시처럼 스택의 제일 위의 값보다 num이 작다면 문제 풀이가 불가능하기 때문에 NO를 출력합니다. 그리고 answer을 출력해주면 됩니다.