문제

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

풀이(첫번째 시도 메모리 초과)

let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n')
let n = input.shift()
    let arr = Array.from({length:n},(v,i)=>n-i)
    let s = [];
    let answer = [];
    while(input != 0){
      if(s && s[s.length-1]===input[0]){
        input.shift();
        s.pop()
        answer.push('-');
      }else{
        if(input.length !== 0 &&arr.length === 0) {
          answer.push('NO')
          break;
        }
        s.push(arr.pop());
        answer.push('+') 
      }
    }
    console.log(answer[answer.length-1] ==='NO' ? 'NO':answer.join('\n'))

[1~N]까지의 배열을 만들어서 while안에서 받아온 배열을 하나씩 뺴주면서 만든 배열과 비교를 했더니 메모리 초과가 나왔다.. 아마 N이 엄청 커졌을때 둘을 비교하는데 엄청 큰 수가 들어가서 그런거 같아서
배열을 만들지 않고 i를 직접 만들어서 문제를 풀어보았다.

두번째 풀이

let input2 = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n')
let n = input2.shift()
let input = input2.map(Number) //1 
    let s = [];
    let answer = [];
    let i = 1; 
    for(let j = 0; j<input.length; j++){ //2
      while(s.length === 0 || s[s.length-1]<input[j]){ 
        s.push(i)
        i++
        answer.push("+")
      }

      if(s[s.length-1] === input[j]){ //3
        s.pop()
        answer.push("-")
      }else{
        answer.push("NO")
        break;
      }
     
    }
    console.log(answer[answer.length-1] ==='NO' ? 'NO':answer.join('\n')) //4

1. 받아온 배열을 Number형으로 새로운 배열에 저장한다.
2. for문으로 받아온 배열을 순회하면서 만약 stack에 가장 마지막으로 들어간 수가 input의 j번째 수보다 작으면 stack 계속 넣어준다.
3. 만약에 stack에 가장 마지막 수가 input의 j번째수와 같다면 stack에서 pop()해주고
   같지 않다면 stack으로 만들 수 없는 배열이므로 answer에 NO를 넣어준다
4. answer배열에 NO가 있으면 stack으로 될 수 없는 배열이므로 NO를 리턴하고 아니면 +,-를 리턴

🌟 시간복잡도에 대해서 한번 더 생각하게 되는 계기가 되었으며 여러개의 배열을 만들어서 반복하는거보다 메모리를 줄이기 위해서 i를 직접 선언해서 하는 방법에 대해서 공부하는 계기가 되었다.