🔴 문제
🟡 Sol
const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const [n, ...inputs] = fs.readFileSync(path).toString().trim().split('\n');
const numbers = inputs.map((it) => Number(it));
let temp = 1;
const stack = [0];
const result = [];
let targetIdx = 0;
while (targetIdx < Number(n)) {
if (stack.length === 0) break;
const i = stack.length - 1;
const target = numbers[targetIdx];
if (stack[i] < target) {
result.push('+');
stack.push(temp);
temp += 1;
} else if (stack[i] === target) {
result.push('-');
stack.pop();
targetIdx += 1;
} else if (stack[i] > target) {
break;
}
}
if (stack.length !== 1) console.log('NO');
else console.log(result.join('\n'));
🟢 풀이
먼저 숫자를 넣을 stack과 어떤 연산을 했는지 넣어줄 result배열을 만들어 준다. 그리고 numbers 배열의 n개의 수열을 하나씩 살펴보면서 스택 수열이 될 수 있는지 확인한다.
그래서 numbers 배열에서 현재 살펴볼 요소를 target이라는 변수로 두고 stack의 마지막 요소가 target보다 작은지, 큰지, 같은지 비교한다.
첫 반복부터 stack의 마지막 요소로 비교를 해야하기 때문에 stack의 초기값으로 0을 넣어준다.
스택 수열은 값을 1부터 넣을 수 있기 때문에 이 상태를 기억할 temp 변수를 하나 만들었다.
만약 stack의 마지막 요소가 target보다 작다면 temp 변수를 stack배열에 푸시하고 이 연산을 기억하기 위해 result에도 +를 푸시해준다.
즉, 첫번째 테스트케이스에서 target인 4보다 작은 1인 경우 스택배열에 넣어준다는 것이다. 1, 2, 3, 모두 넣다보면 4를 푸시할 때가 생길 것이다. 그러면 stack의 마지막 요소가 target과 같아지는 때가 오는데 이때 pop 연산을 진행하준다. 그리고 numbers 배열의 다음요소를 탐색하기 시작한다.
이 과정을 올바르게 진행하게 되면 스택수열이 완성되고 마지막엔 stack에는 0 하나만 남게 된다.
만약 스택수열이 아니라면 stack의 마지막 요소가 target보다 큰 경우가 생길텐데 이 경우 반복을 종료해주면 된다.
반복을 중간에 종료 했으니 stack배열의 길이는 1이 아니게 된다. 이 경우에 NO를 출력해주고 이 경우가 아닌, 반복을 올바르게 종료 했다면 result의 연산순서를 출력해주면 된다.
🔵 Ref
