[백준] 스택 수열 #1874

설명

문제 설명만 보고 무슨 말인지 이해가 가지 않아 유튜브 영상에서 해당 문제에 대한 설명을 들었다. (영상링크)
문제를 이해하니 그냥 Stack 자료구조를 사용해서 쉽게 풀 수 있는 문제였다.
JS에서 stack은 그냥 배열로 사용해도 되지만 이전에 푼 스택문제에서 사용한 Stack class를 가져와서 풀었다.

Node.js 풀이

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const N = Number(input[0]);
const nums = input.slice(1).map(Number);

class Stack {
  constructor() {
    this.stack = [];
  }
  push(value) {
    this.stack.push(value);
  }
  pop() {
    if (this.size() === 0) return -1;
    return this.stack.pop();
  }
  top() {
    return this.size() ? this.stack[this.size() - 1] : -1;
  }
  size() {
    return this.stack.length;
  }
  empty() {
    return this.size() === 0 ? 1 : 0;
  }
}

const solution = (N, nums) => {
  const stack = new Stack();
  let answer = '';
  let max = 0;
  for (const n of nums) {
    if (n > max) {
      for (let i = max + 1; i <= n; i++) {
        stack.push(i);
        answer += '+\n';
      }
      max = n;
      stack.pop();
      answer += '-\n';
    } else {
      if (stack.top() === n) {
        stack.pop();
        answer += '-\n';
      } else {
        return 'NO';
      }
    }
  }

  return answer;
};

console.log(solution(N, nums));

C++ 풀이

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N; cin >> N;
    int max = 0;
    stack<int> S;
    string answer = "";
    while(N--) {
        int x;
        cin >> x;
        if (max < x) {
            for (int i=max+1; i<=x; i++) {
                S.push(i);
                answer += "+\n";
            }
            max = x;
            S.pop();
            answer += "-\n";
        } else {
            if (S.top() == x) {
                S.pop();
                answer += "-\n";
            } else {
                answer = "NO";
                break;
            }
        }
    }
    
    cout << answer;
    return 0;
}