[백준] 1874번 스택 수열 C++ 코드

코드

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

using namespace std;
int n,tmp;
stack<int> stk;
vector<int> v;
vector<char> res;
int main() {
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> tmp;
        v.push_back(tmp);
    }
    int num = 1;
    for(int i = 0; i < v.size(); i++) {
        int o = v[i];
        while(1) {
        	// 같은 값이면 res에 - 추가 및 스택에서 값 제거
            if(stk.size() && (stk.top() == o)) {
                stk.pop();
                res.push_back('-');
                break;
            }
            // 스택이 비어있거나, 스택의 가장 위의 값이 목표 값보다 작은 경우 
            if(stk.empty() || (stk.size() && stk.top() < o)) {
                stk.push(num++);
                res.push_back('+');
                continue;
            }
            // 스택의 가장 위의 값이 목표값보다 큰 경우
            // 이 경우는 수열을 만들 수 없음
            if(stk.size() && (stk.top() > o)) {
                cout << "NO\n";
                return 0;
            }
        }
    }
    for(char i : res) cout << i << '\n';

    return 0;
}

풀이

스택 연산을 통해 주어진 수열을 만들 수 있는지 확인하는 문제이다. while 반복문 안에서 스택의 top이 현재 목표 값인 o와 같다면 결과에 -를 추가하고 반복문을 종료한다. 스택이 비어 있거나 top이 o보다 작으면 스택에 num을 push하고 결과에 +를 추가한 후 num을 1 증가시킨다. 스택의 top이 o보다 크면 이는 스택 수열을 만들 수 없다는 뜻이므로 NO를 출력하고 프로그램을 종료한다.

 

top이 o보다 크면 수열을 만들 수 없는 이유는, 현재 들어온 값이 수열에 추가되지 않은 상태에서 해당 값을 빼주어야 하기 때문이다. 이 값을 빼주면 그 다음에 해당 숫자가 필요할 때 사용할 수 없기 때문에 수열을 만들 수 없다.