[백준 알고리즘/C++/스택] 1874 스택 수열

 

 

문제 해석이 문제인 문제^^..

1부터 n까지의 수를 적절히 push, pop 하여 입력값과 같은 수열을 만들 수 있는지 체크하는 문제

만약 된다면 push는 +, pop은 -로 표현하여 출력하고 안되면 NO를 출력한다

 

 

stack.empty()가 true면 push, false면 stack.top()이 입력값과 같은지 체크한다

같지 않으면 같아질 때 까지 +1 해가며 push하고

같아지면 pop 해주면 됨

 

push, pop 할 때 +, -를 string으로 이어붙여서 마지막에 하나씩 출력하면 된다

마지막에 스택이 비어있지 않다면 NO를 출력한다!

 

 

#include <iostream>
#include <stack>
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int n, input, cur = 1;
    stack<int> s;
    string res;
 
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> input;
 
        if (s.empty()) {
            s.push(cur++);
            res += "+";
        }
 
        while (s.top() != input) {
            if (cur > n) break;
 
            s.push(cur++);
            res += "+";
        }
 
        if (s.top() == input) {
            s.pop();
            res += "-";
        }
    }
    
    if (s.empty()) {
        for (int i = 0; i < res.size(); i++) {
            cout << res[i] << "\n";
        }
    }
    else
        cout << "NO";
}