[프로그래머스 lev2/JS] 택배상자

문제 출처

프로그래머스 lev2 - 택배상자

나의 풀이

1차시도 (50/100, 런타임에러)

런타임 에러가 발생한다. 여전히 크기가 너무 큰 애들은 시간초과가 발생한다.

function solution(order) {
  let curr = []
  for(let i=1; i<=order.length; i++) curr.push(i)
  let idx = 0
  let answer = 0
  let currFront = 0
  let subStack = []
  // console.log(curr)

  while(1){
    let next = answer 
    let box = order[idx]
    // console.log(idx, subStack, curr)
    let cF = currFront

    // currFirst에서 꺼내는 경우 
    if(box === curr[currFront]) {
      idx++
      answer++
      currFront++
    }
    // curr이 아니라 subLast에서 꺼내야 하는 경우 
    else if(box === subStack[subStack.length-1]) {
      idx++
      answer++
      subStack.pop()
    }
    // curr에서 꺼내야 하는데 currFirst이 아닌 경우 
    else if(curr.slice(cF).includes(box)) {
      subStack.push(...curr.slice(cF, curr.indexOf(box)))
      currFront = curr.indexOf(box)+1
      idx++
      answer++
    }

    if(next === answer) break
    if(answer === order.length) break;
  }
  return answer
}


console.log(solution([1, 2, 4, 3, 5]))
console.log(solution([4, 3, 1, 2, 5]))
console.log(solution([2, 1, 4, 3, 6, 5, 8, 7, 10, 9])) // 10
console.log(solution([2, 1, 6, 7, 5, 8, 4, 9, 3, 10])) // 10
console.log(solution([5, 4, 3, 2, 1]))

2차시도 (50/100, 단순실패)

따로 배열을 만들지 않고 index로 값을 찾으려고 했다. 경우의 수도 3가지로 정리를 좀 했다. 런타임 에러는 잡았으나, 안 풀린다. 1~5번은 통과하고, 6~10번이 실패한다.

function solution(order) {
  let curr = []
  for(let i=1; i<=order.length; i++) curr.push(i)
  let idx = 0
  let answer = 0
  let subLast = 0
  let currFirst = 0
  // console.log(curr)

  while(1){
    let next = answer 
    let box = order[idx]

    // currFirst에서 꺼내는 경우 
    if(box === curr[currFirst]) {
      idx++
      answer++
      currFirst++
    }
    // curr에서 꺼내야 하는데 currFirst이 아닌 경우 
    else if(curr.slice(currFirst).includes(box)) {
      subLast = curr.indexOf(box) - 1
      idx++
      answer++
      currFirst = subLast+2
    }
    // curr이 아니라 subLast에서 꺼내야 하는 경우 
    else if(box === curr[subLast]) {
      idx++
      answer++
      subLast--
    }

    if(next === answer) break
    if(answer === order.length) break;
  }
  return answer
}

console.log(solution([1, 2, 4, 3, 5]))
console.log(solution([4, 3, 1, 2, 5]))
// console.log(solution([2, 1, 4, 3, 6, 5, 8, 7, 10, 9])) // 10
// console.log(solution([2, 1, 6, 7, 5, 8, 4, 9, 3, 10])) // 10
// console.log(solution([5, 4, 3, 2, 1]))

3차시도 (60/100, 시간초과)

배열을 쓰되,
subStack.push(...curr.slice(cF, curr.indexOf(box)))
currFront = curr.indexOf(box)+1
부분에서 런타임에러 문제가 생기는 것 같아 while 문으로 돌렸지만 여전히 시간초과가 발생한다.

function solution(order) {
  let curr = []
  for(let i=1; i<=order.length; i++) curr.push(i)
  let idx = 0
  let answer = 0
  let currFront = 0
  let subStack = []
  // console.log(curr)

  while(1){
    let next = answer 
    let box = order[idx]
    // console.log(idx, subStack, curr)

    // currFirst에서 꺼내는 경우 
    if(box === curr[currFront]) {
      idx++
      answer++
      currFront++
    }
    // curr이 아니라 subLast에서 꺼내야 하는 경우 
    else if(box === subStack[subStack.length-1]) {
      idx++
      answer++
      subStack.pop()
    }
    // curr에서 꺼내야 하는데 currFirst이 아닌 경우 
    else if(curr.slice(currFront).includes(box)) {
      let target = curr.indexOf(box)
      while(currFront !== target){
        subStack.push(curr[currFront])
        currFront++
      }
      currFront++
      idx++
      answer++
    }

    if(next === answer) break
    if(answer === order.length) break;
  }
  return answer
}


console.log(solution([1, 2, 4, 3, 5]))
console.log(solution([4, 3, 1, 2, 5]))
console.log(solution([2, 1, 4, 3, 6, 5, 8, 7, 10, 9])) // 10
console.log(solution([2, 1, 6, 7, 5, 8, 4, 9, 3, 10])) // 10
console.log(solution([5, 4, 3, 2, 1]))

다른 풀이 (통과)

나는 삽질을 엄청나게 했다..

생각해보면,

(1)
curr 배열을 만들 필요가 없다.
for(let i=1; i<=order.length; i++) 반복문을 순회하면서 각 회차에 while 문으로 조건을 걸면 되므로..

(2)
하나의 stack으로 모든 경우의 수를 관리할 수 있었다.

일단 무작정 서브 컨테이너에 넣는다. stack.push(i)

넣다가 순서에 맞는 택배박스를 만나면, 그리고 그게 가장 위에 쌓여 있으면, 그때부터 가능한 택배박스를 카운팅하기 시작한다(카운팅한 애들은 당연히 서브 컨테이너에서 빼줘야 한다). stack.pop(), idx++

function solution(order) {
  let idx = 0;
  const stack = [];
  for (let i = 1; i <= order.length; i++) {
    stack.push(i);
    while (stack.length > 0 && stack[stack.length - 1] === order[idx]) {
      stack.pop();
      idx++;
    }
  }
  return idx;
}

참고

프로그래머스 택배 상자 javascript