[백준 1874] 스택 수열 (C#, C++) - soo:bak

문제 링크

1874번 - 스택 수열

설명

스택 자료구조의 push 와 pop 을 활용하여 입력으로 주어지는 수열을 만들 수 있는지 판별하는 문제입니다.

만약, 만들 수 있다면 어떤 순서로 push 와 pop 연산을 수행해야 하는지에 대하여 출력해야 합니다.

이 때, 문제의 조건에 따라 1 부터 n 까지의 숫자에 대하여 순차적으로 스택 연산을 수행해야 함에 주의합니다.

먼저, 주어진 n 개의 수열의 원소들을 순차적으로 탐색하며, 각 원소가 현재 스택의 최댓값 보다 큰지 확인합니다.

이 때, 문제의 조건에 따라 스택의 최대값의 초기값은 1 로 설정합니다.

• 만약, 해당 원소가 현재 스택의 최댓값 보다 크다면, 현재 스택의 최대값이 해당 원소와 같을 때 까지 push 연산을 수행합니다.
  

• 만약, 해당 원소가 현재 스택의 최댓값 보다 작거나 같다면, 해당 원소가 현재 스택의 top 에 있는 숫자와 같은지 확인합니다.
  만약, 같지 않다면 이는 주어진 수열을 스택을 활용하여 만들 수 없다는 것을 의미하므로, 이에 대한 체크를 진행합니다.
  

위 과정을 반복한 후, 주어진 수열을 만들 수 있다면 과정을 수행한 모든 push 와 pop 연산을 문제의 출력 조건에 맞추어 출력합니다.

주어진 수열을 만들 수 없다면, "NO" 를 출력합니다.

C# 에서는 StringBuilder 를 사용하지 않으면 시간 초과 가 됨에 주의합니다.

---

Code

[ C# ]

namespace Solution {
  using System.Text;
  class Program {
    static void Main(string[] args) {

      var n = int.Parse(Console.ReadLine()!);

      var s = new Stack<int>();
      var ret = new List<char>();

      int maxVal = 1;
      bool isPossible = true;
      for (int i = 0; i < n; i++) {
        var ele = int.Parse(Console.ReadLine()!);

        while (ele >= maxVal) {
          s.Push(maxVal);
          ret.Add('+');
          maxVal++;
        }

        if (s.Peek() != ele)
          isPossible = false;

        s.Pop();
        ret.Add('-');
      }

      var sb = new StringBuilder();
      if (isPossible) {
        foreach (char r in ret)
            sb.AppendLine(r.ToString());
      } else sb.AppendLine("NO");

      Console.Write(sb.ToString());

    }
  }
}

[ C++ ]

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin >> n;

  stack<int> s;
  vector<char> ret;

  int maxVal = 1;
  bool isPossible = true;
  for (int i = 0; i < n; i++) {
    int ele; cin >> ele;

    while (ele >= maxVal) {
      s.push(maxVal);
      ret.push_back('+');
      maxVal++;
    }

    if (s.top() != ele)
      isPossible = false;

    s.pop();
    ret.push_back('-');
  }

  if (isPossible)
    for (const auto r : ret)
      cout << r << "\n";
  else cout << "NO\n";

  return 0;
}