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