[자료구조, 스택] BOJ 1874 스택 수열

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

1874번: 스택 수열

 

문제 해결 알고리즘

 

스택 수열에 맞게 출력해주는데 이 때, 스택의 맨 위에 있는 수가 주어진 수보다 크면 스택 수열이 될 수 없으므로 그것만 잘 판별해주자

소스 코드

 

#include <bits/stdc++.h>
using namespace std;

int main(){
  int cur_num = 1;
  int n; cin >> n;
  stack<int> s;
  queue<char> q;
  s.push(cur_num++);
  q.push('+');

  for(int i=0;i<n;i++){
    int k; cin >> k;

    if(s.empty()){
      s.push(cur_num++);
      q.push('+');
    }
    
    if(s.top() > k) {
      cout << "NO";
      return 0;
    }
    while(s.top() != k){
      s.push(cur_num++);
      q.push('+');
    }
  

    
    s.pop();
    q.push('-');
    
  }

  while(!s.empty()){
    s.pop();
    q.push('-');
  }


  while(!q.empty()){
    cout << q.front() << '\n';
    q.pop();
  }
}