Coding Test/Baekjoon

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

예롱메롱 2024. 1. 28. 20:35
728x90
반응형
 

1874번: 스택 수열

1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다.

www.acmicpc.net


📌 접근 방법

  • 벡터에 스택 원리로 숫자를 쌓는다
  • 현재 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;
}
728x90
반응형