1874번: 스택 수열

문제 해설

 

 스택을 이용해서 주어진 수열을 출력할 수 있는가에 대한 문제입니다. 스택의 경우 LIFO 구조를 가지고 있으므로, 순서에 유의하여야 합니다. 예시로 주어진 "5->3->4" 의 경우, 5를 출력하고 나면 스택에 남은 숫자는 {3, 4}입니다. 이 때, 나올 수 있는 수는 더 늦게 스택에 push된 4이므로 4보다 3을 먼저 출력할 수 없습니다. 따라서 NO를 출력해야 합니다. 이후의 설명은 코드를 첨부하도록 하겠습니다.

 

 

코드

 

#include <iostream>
#include <stack>
#include <vector>
#include <cstring>
 
using namespace std;
 
bool isUse[100001];
 
int main() {
 
    int n, now = 0;
    cin >> n;
 
    memset(isUse, false, sizeof(isUse));
 
    //stack을 만든다.
    stack <int> s;
    vector <char> output;
    bool isTrue = true;
 
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
 
        if (now < x) { // 만약 현재 위치보다 출력해야 하는 값이 크다면, 스택에 넣어준다.
            for (int i = now + 1; i <= x; i++) {
                if (!isUse[i]) {
                    s.push(i);
                    output.push_back('+');
                    isUse[i] = true;
                }
            }
            now = s.top();
        }
 
        if (now == x) {
            s.pop();
            output.push_back('-');
            if (!s.empty()) {
                now = s.top();
            }
            else {
                now = 0;
            }
        }
        else {
            isTrue = false;
            break;
        }
    }
 
    if (isTrue) {
        for (auto i : output) {
            cout << i << '\n';
        }
    }
    else {
        cout << "NO\n";
    }
 
    return 0;
}

 

 

제출 결과

 

 

 

문제 출처

 

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

1874번: 스택 수열