[Algorithm] - 백준 1874 스택 수열

조건을 잘 생각해야하는데,

예외조건 중 push 개수와 pop개수가 다른 예제가 생각이 나질 않아서

다른분 소스를 참조해서 넘어가긴 했다.


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

int check[100001];
stack<int> st;

int main() {
int n;
cin >> n;

for (int i = 1; i <= n; i++) {
cin >> check[i];

if (check[i] > n) {
cout << "NO" << endl;
return 0;
}
}

int cnt = 0;
int push_cnt = 0;
int pop_cnt = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (check[i] > cnt) {
st.push(++cnt);
push_cnt++;
}
if (st.top() == check[i]) {
st.pop();
pop_cnt++;
break;
}
}
}

if (push_cnt != pop_cnt) {
cout << "NO" << endl;
return 0;
}

cnt = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (check[i] > cnt) {
st.push(++cnt);
cout << "+" << '\n';
}
if (st.top() == check[i]) {
st.pop();
cout << "-" << '\n';
break;
}
}
}

return 0;
}