[백준/JS] 1874번_스택 수열

https://www.acmicpc.net/problem/1874

1874번: 스택 수열

 

[ 문제 설명 ]

스택에 수를 push 할 때는 반드시 오름차순으로만 push할 수 있다.

예를 들어, 4를 push해야 한다면 1~4까지를 모두 push하고 4를 push할 수 있다.

그리고 스택을 쌓다가 필요한 타이밍에 pop을 하게 되는데, 이 pop을 한 수들을 쭉 나열했을 때, N줄에 걸쳐 입력한 수열과 같아야 한다.

즉, 예제 입력 숫자가 pop한 수들을 나열한 수와 같다. 

 

[ 문제 풀이 과정 ]

처음 예제 입력 1을 예시로 보자. 첫 줄에 8이 주어지므로 1~8까지 while문으로 반복문을 8번 돌려주도록 코드를 짠다.

두번째 줄에서 4가 나오므로 1부터 4까지 스택에 추가가 되어야 한다.

따라서 다시 안에 중첩 while문을 돌려 4번 반복될 수 있도록 해야하는데 여기서 4는 input[1]의 수와 같으므로 0부터 input[1] 수까지 앞서 만든 arr [] 배열안에 '+'를 push 해준다. 그 후 4가 되면 pop을 해줘야하는데 이를 위해 stack [] 배열을 임의로 만들어 두고 이 배열에 4를 push해준다. 즉, 4는 앞선 0을 c변수로 잡아 반복문을 돌릴때마다 그 수를 증가시키고 돌릴때마다 stack에 c를 push해주는 형태로 한다. 

 만약 stack 안에 마지막 요소와 input[i]가 같다면 pop을 해주고 '-'를 push 해준다. 

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n').map(e=>e.replace("\r",""));
const n = input[0];
let i = 1;
let c = 0;
const stack = [];
let arr = [];

while(i <= n){
    while(c < input[i]){
        arr.push('+');
        c++;
        stack.push(c);
    }
    if(stack[stack.length-1] == input[i]){
        stack.pop();
        arr.push('-');
    }
    i++;
}

if(stack.length > 0){
    console.log('NO');
    return;
}

console.log(arr.join('\n'));