스택 수열, 백준 1874번

사실 스택 문제니까 좀 만만하게 봤는데

생각보다 꽤 어려웠고, 로직 외에도 다른 부분에서 신경써야할 게 많아서 

까다로운 문제였다.

 

(출력을 저장하는 부분을 주의해야한다.

처음에는 출력 저장하는 것도 push로 저장했는데, 

문자열이기 때문에 +=로 추가하는 것이 성능에 좋고,

또 console.log로 한줄씩 출력해주는 게 아니라 개행문자를 사용하여 하나의 문자열로 만들어 출력해야한다. )

 

특히 javascript로 된 블로그 포스트가 거의 없어서 java 코드를 참고하기도 했다. 

 

문제:

1~n까지의 수를 오름차순으로 스택에 쌓아갈 때(push). 주어진 수열과 비교하여 수열의 인덱스 순서대로,

수열 현 인덱스와 일치하는 숫자가 스택 탑에 있을 때, 스택에서 꺼내서(pop) 수열을 만드는 문제이다.

물론 만들 수 없을 때도 있다. 찾고자 하는 숫자가 현 스택의 탑에 있어야 하기 때문에 스택 탑이 아닌

더 아래에 있으면 만들 수 없기 때문이다. 

 

해결방법1

가장 기본적인 해결방법이다.

var fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString().split('\n');
let array = input.map((element) => 
Number(element))

let length = array.shift()
let stack = []
let flag = []

function stackSequence(){

  for(let i = 1; i <= length; i++){
    /* 스택에 오름차순으로 넣기 */
    stack.push(i)
    flag += '+\n'

    /* stack의 top 확인하기 */
    while(stack.length > 0 && array[0] !== undefined
    &&stack.slice(-1)[0] === array[0]){
      stack.pop()
      flag += '-\n'
      array.shift()
    }
  }

  while(stack.length > 0){
    return 'NO'
  }

  return flag
}

let result = stackSequence()
if(result === 'NO'){ console.log(result)}
else{
  console.log(result.slice(0,-1))
}

스택 하나 쌓고, TOP과 수열 비교하기

주의할 점은 pop한 후에 다시 스택을 쌓는 게 아니라  pop한 스택의 탑과 수열을 다시 비교해본다.

n번의 루프를 돌게 된 후 스택이 비어있으면 수열과 모두 일치하여 pop되었다는 것이기 때문에 

스택이 비어있지 않으면 NO를 리턴해준다. 

 

기본적으로 O(N^2)이 걸리는 문제지만 로직을 조금조금씩 바꿔서 최대한 짧은 시간이 걸리게 만들 수 있다. 

사실 처음에 출력 때문에 시간초과가 되는 줄 모르고  O(N^2)으로 안 만들어보려고 최대한 노력했지만

앞의 코드와 시간도 비슷하게 걸리고 공간도 비슷하게 많이 쓴다. 

top이 아니면 다음 수를 push하고 같으면 계속 pop하는 로직은 똑같기 때문에

결국 루프는 거의 같게 돌게 된다.

var fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString().split('\n');
let array = input.map((element) => 
Number(element))

let length = array.shift()
let stack = []
let flag = []

function stackSequence(){

  let i = 0; 
  while(length >= i){
 
    /* stack의 top 확인하기 */
    if(stack.length > 0 && array[0] !== undefined
    &&stack.slice(-1)[0] === array[0]){
      stack.pop()
      flag += '-\n'
      array.shift()
    }else{
      i++
      stack.push(i)
      flag += '+\n'
    }
  }
  stack.pop()
  flag = flag.slice(0, -3)

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

  return flag
}

let result = stackSequence()
if(result === 'NO'){ console.log(result)}
else{
    console.log(result)
}

 

그렇다면 push하고 top 쳐다보고 push하고 top 쳐다보는 게 아니라

다음 수열의 숫자가 나올 때까지 top과 비교하지 않고 계속 push한다면 어떨까?

어차피 push하고 pop하는 이유는 다음 수열의 숫자와 비교하기 위함이기 때문이다.

O(N^2)이지만 N 하나를 굉장히 줄일 수 있는 방법이다.

 

여기서 value는 비교하고자 하는 수열의 숫자를 말한다. push의 목표가 된다.

목표치까지 push를 다했으면 start를 이전 목표값으로 갱신해준다. 

만약에 4 3 6 8 7 5 2 1 이라는 수열이 있을 때, 

 

우선 첫번재 목표는 4이기 때문에 4까지 달리고 start에 4를 저장해둔다. 그러면 다음에는 stack에 5를 쌓을 수 있게 된다. 

그리고 도착했기 때문에 pop(-)을 해준다.

그리고 다음 목표는 3이 될 텐데 value인 3보다 start인 4가 더 크기 때문에 push는 어렵고,

다시 top이랑 비교해준다. 이때 top이랑 3이 다르다면 스택 수열이 불가능한 것이고,

맞다면 계속 그 과정을 진행해주면 된다. 

이렇게 하면 push하면서 계속 top이랑 비교하는 시간을 줄일 수 있기 때문에 시간이 굉장히 줄어들게 된다. 

실제로 앞의 두 코드보다 시간이 10배 가량 줄어들게 되었다.

var fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString().split('\n');
let array = input.map((element) => 
Number(element))

let length = array.shift()
let stack = []
let flag = ""

function stackSequence(){

  let start = 0
  for(let j=0; j < length; j++){
 
    let value = array[j]
    //console.log("value", value)
    /* 우선 push */
    if(value > start){
      //console.log("start",start)
      for(let i = start+1; i <= value; i++){
        stack.push(i)
        flag += "+\n"
      }
      /* 다시 start 지점 세우기 */
      start = value
    }
    else if(stack[stack.length -1] !== value){
      return 'NO'
    }
    
    /* value에 도착 */
    flag += "-\n"
    stack.pop()
    
  }
  return flag
}

let result = stackSequence()
if(result === 'NO'){ console.log(result)}
else{
  console.log(result.slice(0, -1))
}