[1874] 스택 수열

---

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

1874번: 스택 수열

스택 문제이다.

조금 생각이 필요했다.

 

문제 이해 자체가 조금 힘들었는데,

1~n까지 수에 대해 오름차순으로 입력 받는다고 가정할 때 push, pop의 순서를 출력하는 문제이다.

 

 

백준에 나온 예제를 예시로 들어보면

이렇게 된다.

직접 써보니 일단 push를 먼저한 후, 조건에 따라 pop을 해야겠다고 생각했다.

대신 pop을 할 수 있는 조건이 되지 않는 경우 NO를 출력하고 프로그램을 종료시켰다.

 

 

안되는 조건은? stack의 top이 입력받은 수와 일치하지 않는 것이다.

1 -> 2-> 5 -> 3 -> 4 순으로 출력이 되어야하는데, 실제로 stack에 넣어보면 1 -> 2 -> 5 -> 4 -> 3 순으로 출력된다. 

 

 

조건은 아래 코드에 자세히 나와있다.

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

int N; 
vector<char> myvector; // 배열의 크기를 지정해도 되지 않아서 편리하네용
stack<int> mystack;

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

	cin >> N;

	int before = 0; // 어디까지 push 했는지 기억하기 위한 변수
	bool isWrong = false; // for문 탈출을 위한 변수
	for (int i = 0; i < N; i++) {
		int temp; cin >> temp;
		if (before < temp) { // temp까지 push를 해야되는 상황
			for (int j = before + 1; j <= temp; j++) { 
				myvector.push_back('+');
				mystack.push(j); // push
			}
			before = temp; // 어디까지 push했는지 저장
		}
		if (mystack.top() == temp) { // 입력된 수와 top()이 같으면 
			myvector.push_back('-');
			mystack.pop(); // pop
		}
		else { // pop할 때 원하는 원소가 튀어나오는게 아니라면
			cout << "NO";
			isWrong = true;
			break; // 종료
		}
	}
	if (!isWrong) {
		// 수열을 만들 수 있는 경우
		for (int i = 0; i < myvector.size(); i++) {
			cout << myvector.at(i) << "\n"; // push, pop 출력
		}
	}
}

맨 처음에는 +, -를 배열에 담으려고 했으나, 크기를 지정해야하는데 솔직히 계산하기 귀찮아서 vector로 만들었다.