백준 1874 S2 스택 수열

생성 2025-03-03

문제: 스택 수열

풀이 접근

문제에서 주어진 $n$ 이 $100,000 = 10^6$ 까지 커질 수 있으므로, $O(n)$ 선에서 끝내는 것이 좋아 보임
이미 오름차순으로 주어진 1 .. n 까지 수열이 있고, 이 순서대로만 스택에 푸시할 수 있다는 제약이 존재함
답으로 들어온 수열을 만들수 있냐, 없냐만 판단하면 됨.

그래서 다음 과 같이 풀이하기로 하였다.

어떤 수학적인 해가 존재함을 고심하기보다, 그냥 스택에 넣고 빼는 것을 직접 해보면서 중간에 예외가 발생하면 빠르게 종료.
- 스택 연산을 끝까지 적용해 주어진 수열을 만들 수 있다 하더라도, 주어진 수열을 딱 한 번만 훑으면 되므로 최대 $O(n)$ 임.

알고리즘

1 .. n 오름차순 수열에서 다음에 스택에 넣을 수 있는 수를 cur라고 하자.
만드려는 수열을 seq라고 하고, 연산자 문자의 배열을 pr이라고 하자.
스택 st를 하나 선언한다. 초기에는 cur은 1이다.
- 이는 다음에 스택에 넣을 수 있는 수는 1이고, 현재는 아무 것도 들어 있지 않다는 뜻이다.
seq의 각 원소 seq_num을 순서대로 순회하면서 다음을 진행하자:
- cur이 만일 seq_num이하라면,
  - cur을 하나씩 증가시키면서 스택에 계속해서 오름차순 수열의 원소를 넣어준다.
  - 또한, 현재 seq_num을 st의 탑으로 이동시켜 팝 함으로서 주어진 수열을 만드려고 계속 푸시하고 있는 것이므로, pr에도 '+'를 푸시할 때마다 계속 넣어준다.
- 그리고, 스택이 비어있지 않고, 스택의 탑이 seq_num이라면:
  - 이러면 실제로 지금 스택에서 하나를 꺼내서, seq_num을 만들 수 있다는 뜻이다.
  - 또한, 팝이 일어났으므로 pr에도 '-'를 넣어준다.
- 만일 스택이 비어있거나, 스택의 탑이 seq_num이 아니라면:
  - 뭔가 잘못된 것이므로 종료 처리한다.
만일 seq_num을 다 순회했고 빠른 종료 처리가 안 되었으면 pr을 출력한다.

조금 쉬운 말로 해보면 아래와 같다.

위 알고리즘을 보면 알겠지만 cur을 증가시키기만 하지, 감소시키지는 않는다.

cur은 이번 순회의 seq_num이 (1) 이전에 스택에 넣었던 것인지, (2) 앞으로 넣어햐 하는 것인지 판단하기 위한 변수이다.

(1) 이전에 스택에 넣었다면, 실제로 스택의 탑을 확인하여 그 수가 나오는지 확인한다.

(2) 앞으로 넣어야 한다면, 실제로 넣으면 된다.

문제를 너무 어렵게 생각하지 말자. 아래는 코드이다.

코드

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

int main() {
  int n; cin >> n; // n in [1, 100'000]

  vector<int> seq(n);
  for (int i = 0; i < seq.size(); ++i) {
    cin >> seq[i];
  }

  // cur 는 1,  2, ... ,n 수열에 의거하여, 
  // 다음에 스택에 넣을 수 있는 수
  // cur - 1 까지는 스택에 이미 push 되었다고 보면 됨
  int cur = 1;
  stack<int> st;
  vector<char> pr; pr.reserve(n); // '+', '-' 저장용
  bool is_possible = true;

  for (int const &seq_num: seq) {
    while (cur <= seq_num) {
      st.push(cur);
      pr.push_back('+');
      ++cur;
    }

    if (!st.empty() && st.top() == seq_num) {
      st.pop();
      pr.push_back('-');
    } else {
      is_possible = false;
      cout << "NO";
      break;
    }
  }

  if (is_possible) {
    for (char const &c: pr) cout << c << '\n';
  }
}