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

문제

1874번: 스택 수열

---

문제 설명

일련의 수열을 만들기 위한 스택 연산을 +, -로 출력한다. +는 push, -는 pop을 뜻한다.

---

코드

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

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

    int n; cin >> n;
    int idx = 0;
    int MAX = 1;

    bool fail = false;

    vector <string> calc;
    vector <int> save;
    stack <int> stk;

    for (int i = 0; i < n; i++) {
        int num; cin >> num;
        save.push_back(num);
    }

    stk.push(1);
    calc.push_back("+");

    while (idx < n) {
        if (fail) {
            cout << "NO\n";
            return 0;
        }

        if (stk.empty()) {
            stk.push(MAX + 1);
            calc.push_back("+");

            if (MAX < stk.top()) MAX = stk.top();
            continue;
        }

        if (save[idx] > stk.top()) {
            for (int i = MAX + 1; i <= save[idx]; i++) {
                stk.push(i);
                calc.push_back("+");
            }
        }

        else if (save[idx] < stk.top()) fail = true;

        else {
            if (MAX < stk.top()) MAX = stk.top();
            stk.pop();
            idx++;

            calc.push_back("-");
        }
    }

    for (auto it : calc) cout << it << '\n';
}

---

코드 설명

핵심은 수열의 값과 스택의 최상위 값 비교, 수열의 인덱스 관리이다.

• 수열의 값 > 스택의 최상위 값 : 지금까지 스택에 넣은 값 중 최대값 + 1부터 수열의 값까지 push. 단, 수열의 인덱스는 그대로 둔다.
• 수열의 값 = 스택의 최상위 값 : 최대값 갱신 후 스택의 최상위 값을 pop. 단, 수열의 인덱스를 +1 증가시켜 준다.
• 수열의 값 < 스택의 최상위 값 : 스택 수열을 만들 수 없는 구조이므로 0을 출력 후 프로그램 종료.

---

여담

스택 또는 큐를 사용할 때, empty( ) 함수나 top( ) 함수를 조심해서 사용해야 하는 불편함이 있다.

이를 해소하고자, 맨 처음에 무의미한 값 등[ex. -1, '0']을 push 해두면 empty와 top을 나름 자유롭게 구사할 수 있다.

다만 만능은 아니므로 필요한 때에 적절히 사용하도록 하자.