[C/C++ 백준 1874번] 스택 수열 (Silver 3)

www.acmicpc.net/problem/1874

언뜻보면 어려워 보이지만, 규칙이 굉장히 단순하기 때문에 조금만 생각해도 풀 수 있던 문제였던 것 같다.

큰 수가 입력되면 해당수까지 스택에 숫자를 쌓은 뒤 빼고, 낮은 수가 입력되면 스택에서 숫자를 빼어 해당수가 나오는지 비교한다. 위 행동을 위해 스택에 숫자를 오름차순으로 넣는 스택2, 그리고 문제에서 다루는 스택인 스택1로 나누어 해결했다.

 

#include <cstdio>
#include <stack>
using namespace std;
int main(void){
   int N, num, totalcnt=0;
   bool ok = true;
   scanf("%d", &N);
   stack <int> stk1;
   stack <int> stk2;
   queue <char> ans;
   for(int i=0; i<N; i++){
      stk2.push(N-i);
   }
   for(int i=0; i<N; i++){
      scanf("%d", &num);
      if(totalcnt<num){
         for(int j=0; j<num-totalcnt; j++){
            int tmp = stk2.top();
            stk2.pop();
            stk1.push(tmp);
            ans.push('+');
         }
         totalcnt = num;
         stk1.pop();
         ans.push('-');
      }
      else{
         if(stk1.top()==num){
            stk1.pop();
            ans.push('-');
         }
         else{
            ok = false;
         }
      }
   }
   if(!ok){
      printf("NO");
   }
   else{
      while(!ans.empty()){
         printf("%c\n", ans.front());
         ans.pop();
      }
   }
}