[BOJ] 1874: 스택 수열

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

 

 

 

 

#include <bits/stdc++.h>
using namespace std;
stack<int> s;
vector<char> v;
int n;
int perm[100000];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n;
  for (int i = 0; i < n; i++) cin >> perm[i];
  for (int k = 1, i = 0; k <= n; k++) {
    s.push(k);
    v.push_back('+');
    while (!s.empty() && (s.top() == perm[i])) {
      s.pop();
      v.push_back('-');
      i++;
    }
  }

  if (s.empty())
    for (char c : v) cout << c << '\n';
  else
    cout << "NO" << '\n';
}

주어진 수열을 만들 수 있는지 확인하기 위해서는 숫자를 1부터 스택에 차례대로 넣을 때마다

스택의 top이 수열의 앞부분이랑 일치하는지 확인해야 한다.

 

일치한다면 pop연산을 수행해서 해당 숫자를 꺼내고, 스택의 top이 수열의 다음 숫자와 같은지 또 확인하면 된다.

이 과정을 반복해서 마지막에 스택이 empty라면 주어진 수열을 만들 수 있는 것이다.

 

주의할 점은 스택의 top과 수열을 앞부분을 비교할 때 스택이 empty인지 확인해야 한다.

empty인 스택의 top에 접근하면 런타임 에러가 발생하기 때문이다.