[C++] 백준 1874번 : 스택 수열

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

1874번: 스택 수열

---

 문제 풀이

1부터 n까지 숫자들을 스택을 이용해서 처음에 입력받은 수열을 구현하는 문제이다.

{1, 2, 5, 4, 3}의 수열을 구현하기 위해서는

push, pop, push, pop, push, push, push, pop, pop, pop의 과정을 거치면 된다. 

구현할 수 없는 경우에는 "NO"를 출력해주면 된다.

수열에서 나올 수 있는 경우는 다음과 같다.

 1. 스택이 비어있을 때 (PUSH)

 2. 스택의 TOP이 수열의 값과 같을 때 (POP)

 3. 스택의 TOP과 수열의 값이 다를 때 (PUSH)

 4. 사용할 수 있는 모든 수를 사용하고 스택의 TOP이 수열의 값과 다를 때 (NO)

이 경우들만 구현하면 된다.

 느낀 점

재밌는 문제였다. 마지막에 "no"가 출력될 조건을 구현하기 위해서 따로 조건을 만들까 생각했는데 단순하게 코드 한 줄만 넣어주면 되는 부분이었다. 이번 기회로 조건의 순서가 코드에 큰 영향을 줄 수 있다는 것을 느꼈다.

 코드

#include <iostream>
#include <stack>
#include <string>

using namespace std;

int n;
int arr[100001];
stack<int> s;
string result;

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

	cin >> n;
	for (int i = 0; i < n;i++) {
		cin >> arr[i];
	}

	int num = 1, idx = 0;
	while (true) {
		if (num > n && s.empty()) break;
		if (num > n && s.top() != arr[idx]) {
			result = "NO\n";
			break;
		}
		else if (s.empty() || s.top() != arr[idx]) {
			s.push(num++);
			result += "+\n";
		}
		else if (s.top() == arr[idx++]) {
			s.pop();
			result += "-\n";
		}
	}
	for (auto a : result) {
		cout << a;
	}
}