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

https://school.programmers.co.kr/learn/courses/30/lessons/131704

 

 

---

 

문제요점

• 1번부터 n번까지 증가하는 순으로 벨트에 놓여있다.
• 1번부터 순서대로 상자를 내릴 수 있다.
• 현재 실을 순서가 아니면 보조컨테이너에 보관 => 보조컨테이너는 마지막에 보관한 상자부터 꺼내게 된다 stack
• 보조를 사용해도 순서대로 싣지 못하면 더이상 상자를 싣지 않는다
• 실을 수 있는 상자 갯수 리턴

 

풀이

 

기존의 상자 순서대로 진행할 때, 다음상자와 보조컨테이너의 마지막 상자를 체크한다 O(nlogn)

 

• 상자를 1부터 n개까지 순회하며 현재 실어야하는 순서인지 확인한다
• 컨테이너벨트에 상자가 있으면 옮기고
• 보조컨테이너벨트(stack)의 마지막에 상자가 있으면 stack의 마지막 상자를 옮긴다
•  이 둘다 없으면 보조컨테이너 stack로 상자를 옮긴다

 

최종코드

function solution(order) {
    var answer = 0;
    let boxNum = 1;
    let orderIndex = 0;
    let stack = []; // 보조벨트
    
    // 넣은 상자 갯수가 전제박스 개수보다 작거나 같을때
    while(boxNum <= order.length+1) { // boxNum이 1부터 시작
        // 컨테이너벨트에 있을때
        if (order[orderIndex] === boxNum) {
            boxNum++;
            answer++;
            orderIndex++;
            continue;
        }
        // 보조컨테이너벨트에 있을때
        if (stack.length && order[orderIndex] === stack[stack.length-1]) {
            answer++;
            orderIndex++;            
            stack.pop();
            continue;
        }
        // 둘다 없을때 보조컨테이너에 저장
        stack.push(boxNum);
        boxNum++;
    }
    return answer;
}

 

 

또다른 풀이

function solution(order) {
  var answer = 0;
  const stack = [];
  const len = order.length;
  let index = 0;
  let currOrder = order[index];
  // 기존 컨테이너벨트 순회
  for (let i = 1; i <= len; i++) {
    // 실을 순서인 경우
    if (i === currOrder) {
      answer++;
      currOrder = order[++index]; // 다음 실을 순서
    }
    // 실을 순서가 아닌 경우
    else {
      // 보조가 실을 순서라면
      if (stack.length && stack[stack.length - 1] === currOrder) {
        answer++;
        stack.pop();
        currOrder = order[++index];
        i--;
      } else {
        // 보조에 실는다
        stack.push(i);
      }
    }
  }
  // 보조컨테이너 순회
  while (stack.length) {
    // 보조컨테이너의 상자를 실어야하는 경우
    if (stack[stack.length - 1] === currOrder) {
      answer++;
      stack.pop();
      currOrder = order[++index];
    } else {
      break;
    }
  }
  return answer;
}

 

느낀점

shift는 다른 모든 요소를 한 칸씩 앞으로 이동시켜야 하므로 시간복잡도는 O(n)이다

O(nlogn)으로 for문 안에서 shift를 사용하면 시간초과가 나므로 index를 사용하여 shift를 대체할 수 있다.

혹은 큐의 shift를 직접 구현할 수 있다.

pop은 다른 요소들을 이동시킬 필요가 없으므로 O(1) 이다