[BOJ 백준] 1874번 스택 수열

문제

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

1874번: 스택 수열

접근

스택(LIFO : 후입선출)으로 문제에서 주어지는 수열을 만들 수 있는지 확인하는 문제이다. 후입선출 구조란 말 그대로 늦게 들어온 자료가 가장 먼저 나가는 구조를 뜻한다. 양동이 모양을 생각하면 편할 것이다. 이러한 후입선출 구조를 생각해서 코드를 짜면 쉽게 해결할 수 있는 문제이다.

코드

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n, a, chk = 1;
    vector<int> v;
    vector<char> ans;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a;
        if (v.size() == 0 || v[v.size() - 1] != a) {
            if (chk > a) {
                cout << "NO";
                return 0;
            }
            while (chk != a) {
                v.push_back(chk);
                ans.push_back('+');
                chk++;
            }
            ans.push_back('+');
            ans.push_back('-');
            chk++;
        } else if (v[v.size() - 1] == a) {
            v.pop_back();
            ans.push_back('-');
        }
    }
    for(int i = 0; i < ans.size(); i++)
        cout << ans[i] << "\n";
    return 0;
}

 

깃 허브 주소 : https://github.com/algoribi/algorithm-study