[BOJ/백준/C++] 1874번

1874번: 스택 수열

---

반응형

📌 접근 방법

• 벡터에 스택 원리로 숫자를 쌓는다
• 현재 target으로 하는 숫자가 1에서 1씩 키워가면서 target이 벡터에 있는 숫자가 될 때까지 push를 해준다
  • 임시 벡터에 push해줌 (string 변수에 + 저장)
  • 벡터에 있는 숫자를 빼야하기 때문에 pop 해줌(string 변수에 - 저장)
• 다음 벡터에 있는 숫자가 임시 벡터의 top에 있을 경우 pop해주고 임시벡터에 없을 경우 위 과정을 반복한다.(target은 이어서 진행!)
• 해당 수열로 만들 수 없을 경우  No를 출력
• 만들 수 있는 경우 String 변수에 있는 기호들 한줄씩 출력

 

✅  Pass Code

#include<iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<iterator>
#include<map>
#include<set>
#include<unordered_set>
#include <stack>
using namespace std;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin>>n;

    string result="";
    vector<int>v;
    for(int i=0; i<n; i++){
        int x;
        cin>>x;
        v.emplace_back(x);
    }
    vector<int>num;
    int j=0;
    for(int i=1; i<=n; i++){
        num.emplace_back(i);
        result+='+';
        while(!num.empty()&&num.back()==v[j]){
            num.pop_back();
            result+='-';
            j++;
        }

    }
    if(!num.empty()){
        cout<<"NO\n";
    }
    else{
        for(int i=0; i<result.length(); i++){
            cout<<result[i]<<'\n';
        }
    }

    return 0;
}