[BOJ] 1874번 스택수열 C++

문제

https://www.acmicpc.net/problem/1874

풀이

c++은 stack이 STL로 구현이 되어있어 이를 이용하여 문제를 풀었다.

스택은 후입 선출(Last-In-First-Out, LIFO)의 특성을 가지고 있다.

이를 이용하여 수열을 만들기 위해 push와 pop연산의 순서를 저장하는 char 배열을 만들고 배열의 인덱스를 옮겨줄 int형 변수 resultIndex를 만들었다.

배열이 비어있으면 첫 번째 값을 push 하고 result 배열에 '+'를 저장한다.

그 이후부터는 스택의 top과 다음으로 pop연산이 되어야 하는 수를 비교하여 top이 더 작다면 그 수와 같아질 때까지 push 연산을 하고 같아지면 그 수를 pop 함으로써 수열을 만들어준다.

수열이 만들어지지 않는 예외의 경우는 스택의 top 값이 다음으로 pop 되어야 하는 수보다 더 큰 경우이다. 그 이유는 pop 되어야 하는 수는 스택 안에 저장이 되어있을 것이고 이를 pop 하기 위해서는 그 값 위에 있는 다른 값을 먼저 pop을 하게 되어 수열이 만들어지지 않는다.

소스코드

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

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    stack<int> s;
    
    int n;
    cin >> n;
    
    char result[2*n];
    int value = 1;
    int resultIndex = 0;
    int a;
    bool N=true;
    
    for(int i=0; i<n; i++){
        cin >> a;
        while(true) {
            if(s.empty()) {
                s.push(value++);
                result[resultIndex++] = '+';
            }
            if(s.top() < a){
                s.push(value++);
                result[resultIndex++] = '+';
            }
            if (s.top() == a) {
                s.pop();
                result[resultIndex++] = '-';
                break;
            }
            if(s.top() > a){
                N = false;
                break;
            }
        }
    }
    if(N){
        for (int i=0;i<resultIndex;i++) {
            cout << result[i] << '\n';
        }
    }else{
        cout << "NO";
    }
}