[백준/C++] 1874번 스택 수열

1874번 스택 수열

문제

1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.

입력

첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.

출력

입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.

풀이

이중 반복문을 사용해 스택에 값을 push 하거나 입력받은 수열의 값과 스택의 최상단 값을 비교한다. 따라서 시간복잡도는 O(n^2)이다.

1. 길이가 n인 수열의 i번째 값을 입력받는다. 이를 n번 반복한다.
2. 만약 입력받은 값 j보다 스택에 삽입하는 정수 k가 작다면 스택에 k를 push한다. 그 후 k를 증가시키고 "+"를 문자열 answer에 합친다. 앞의 조건에 만족할 때까지 반복한다.
3. 만약 스택의 최상단 값이 입력받은 값과 같다면 pop한다. 이때 "-"를 문자열 answer에 합친다.
4. 스택의 최상단 값과 입력받은 값이 다르다면 스택으로 수열을 만들 수 없다. 따라서 문자열 answer을 "NO"를 대입하고 반복문을 종료한다.
5. 결과값을 출력한다.

코드

#include <iostream>
#include <string>
#include <stack>
using namespace std;

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

  int n, k = 0;
  cin >> n;
  stack<int> st;
  string answer = "";

  // 길이가 n인 수열의 i번째 수와 비교
  for (int i = 0, j; i < n; i++)
  {
    cin >> j;

    // k부터 입력받은 값까지 k를 1씩 증가시키면서 stack에 push
    while (k < j)
    {
      st.push(++k);
      answer += "+\n";
    }

    // 스택이 비어있지 않고
    if (!st.empty())
    {
      // 스택의 최상단 값이 입력받은 값과 같다면 pop
      if (st.top() == j)
      {
        answer += "-\n";
        st.pop();
      }
      // 스택의 최상단 값이 입력받은 값과 다르다면 NO
      else
      {
        answer = "NO";
        break;
      }
    }
  }
  // 결과값 출력
  cout << answer;
  return 0;
}