[BOJ # 1874] 스택 수열

주어진 문제는 위와 같다. 수열의 크기 n 이 주어지고, 수열을 이루는 1 ~ n 까지 정수가 하나씩 순서대로 주어진다. 이 때, 스택을 가지고 주어진 수열을 만들기 위해 필요한 연산을 한 줄에 하나씩 출력한다.

 

스택은 LIFO 구조로, push / pop 연산을 통해 자료를 저장하고 뺄 수 있다. 스택으로 수열을 만들기 위해서 필요한 조건은, 주어진 정수가 항상 스택에 저장된 top 값보다 크거나 같아야 한다는 것이다. 만약 스택의 top 에 저장된 값보다 작은 정수가 주어졌을 때는 그 값을 찾기 위해 스택에서 여러 번 pop 을 해야 하므로, 이 문제에서 주어진 조건을 만족할 수 없다.

 

때문에 문제의 풀이 방식은 간단하다. 주어진 정수가 스택에 저장된 top 의 값보다 크다면 값들을 push 해 주어진 정수가 스택에 저장되도록 한다. 그 뒤 스택의 top 에 있는 값을 꺼내면 된다. 만약 주어진 정수가 스택에 저장된 top 값과 같다면 그 값을 pop 연산을 통해 바로 꺼낼 수 있다. 이 때 문제는, 이미 스택에 push 된 값이 다시 push 될 수 있다는 점이다.

 

예를 들어, [1, 2, 3, 4] 의 순서로 push 가 이뤄지고 [4, 3] 순서로 pop 이 되었을 때 스택의 top 에 저장된 값은 '2' 이다. 이 때 '6' 이라는 정수가 주어지면 스택의 top 보다 큰 '3' 부터 '6' 까지 [3, 4, 5, 6] 순서로 push 를 하게 된다. 하지만 이 경우에 이미 [3, 4] 라는 값들은 push / pop 이 된 값이므로 이를 다시 수행하지 않도록 따로 기록을 해야 한다.

 

그래서 이 문제에서 추가적으로 활용하는 변수로 스택에 마지막으로 push 된 값을 기록한다. 만약 위의 경우에 마지막으로 push 한 값이 '4' 임을 안다면 '6' 이 주어졌을 때, [5, 6] 만 push 를 하면 됨을 알 수 있다. 따라서 중복되는 push / pop 연산이 이루어지지 않는다.

 

이러한 풀이로 작성한 소스 코드는 다음과 같다.

 

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

int N, num, cur;
stack<int> s;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string ans = "";
    cin >> N;

    for (int i = 0; i < N; i++) {
        cin >> num;

        if (cur < num) {
            for (int k = cur + 1; k <= num; k++) {
                s.push(k);
                ans += "+\n";
            }
            cur = num;
        }
        else if (s.top() != num) {
            ans = "NO\n";
            break;
        }

        s.pop();
        ans += "-\n";
    }

    cout << ans;
}

문제 풀이 중간에 불가능한 값이 입력될 경우 ans 라는 문자열을 "NO" 로 바꾸고 반복을 종료한다. 그렇지 않을 경우 정상적으로 연산의 순서가 ans 에 저장될 것이다. 이를 콘솔에 출력함으로써 주어진 문제에 대한 답을 얻을 수 있다.