#1874번 스택 수열 (C++)

링크 : www.acmicpc.net/problem/1874

1874번: 스택 수열

이 문제는 대충 훑어보고서는 이해가 안될 수 있다. 

문제 해석은 다음과 같다. 

 

1부터 n까지 숫자가 차례대로 입력되며, push로 입력을 하고 pop을 통해 숫자를 제거한다. 

pop으로 제거된 숫자가 입력된 값과 동일한지를 비교하면 되는데, 아래 예제 입력1의 해설을 보면 이해된다.

---

1. + + + + -> 이 과정으로 1, 2, 3, 4가 누적된다.

문제에서 1이상 n이하의 숫자가 오름차순으로 push된다고 언급했다.

 

2. - - -> 이 과정으로 4와 3이 순차적으로 제거된다.

Stack이니 LIFO(Last in First Out) 방식으로 숫자가 제거된다.

그리고 이는 예제 입력의 첫 번째, 두 번째 값과 일치한다. 

 

3. + + -> 이 과정으로 5 6이 누적된다. 현재까지 남아있는 숫자들은 1 2 5 6이 된다. 

 

4. - -> 이 과정으로 6이 제거된다.

그리고 이는 예제 입력의 세 번째 값과 일치한다. 

(이하 생략)

---

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


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

	int n = 0, j = 0, cnt = 1;
	stack<int> s;
	vector<char> v;
	int arr1[100001];
	cin >> n;
	for (int i = 0; i < n; i++) cin >> arr1[i];
	s.push(1);
	v.push_back('+');
	while (j < n) {
		if (cnt > n) break;
		if (s.empty()) {
			cnt++;
			s.push(cnt);
			v.push_back('+');
		}
		else if (s.top() == arr1[j]) {
			s.pop();
			v.push_back('-');
			j++;
		}
		else {
			cnt++;
			s.push(cnt);
			v.push_back('+');
		}
	}
	if (s.empty()) {
		for (int i = 0; i < v.size(); i++) cout << v[i] << "\n";
	}
	else cout << "NO" << "\n";
	return 0;
}

Stack이 비어있는 경우 -> 런타임 에러 발생

"NO"가 출력되어있는 상황을 고려못함 -> 무한 루틴에 빠짐

이 두가지를 고려하지 못해 첫 시도에서는 틀려버렸다.