[Javascript] 프로그래머스 - 택배상자

문제 설명

컨테이너 벨트에서 주어진 순서대로 택배 상자를 트럭에 실어야 합니다. 하지만 컨테이너 벨트는 한 방향으로만 진행되며, 원하는 순서대로 적재할 수 없는 경우 보조 컨테이너 벨트를 사용해야 합니다. 보조 컨테이너 벨트는 스택(Stack) 구조로, 가장 최근에 보관한 상자부터 꺼낼 수 있습니다. 이를 이용해 최대한 많은 상자를 트럭에 실을 수 있는 개수를 구하는 문제입니다.

---

제한 사항

• order의 길이는 1 이상 1,000,000 이하입니다.
• order 배열에는 1부터 order.length까지의 정수가 한 번씩 등장합니다.
• order[i]는 order[i] 번째 상자를 i+1 번째로 트럭에 실어야 함을 의미합니다.

---

해결 방법

알고리즘: 스택을 활용한 그리디 알고리즘

1. 컨테이너 벨트에서 상자를 하나씩 확인하며, 현재 트럭에 실어야 하는 순서(order)와 비교합니다.
2. 만약 현재 상자가 order에 해당하면 즉시 트럭에 적재합니다.
3. 그렇지 않다면, 보조 컨테이너 벨트(스택)에 저장합니다.
4. 상자를 실을 때마다 보조 컨테이너 벨트의 마지막 값과 order를 비교하여 순서가 맞다면 꺼내어 적재합니다.
5. 위 과정을 반복하여 최대한 많은 상자를 적재합니다.

---

시간 복잡도

• 각 상자는 한 번만 컨테이너 벨트에서 확인되고, 보조 컨테이너 벨트(스택)에 push 및 pop 연산이 수행됩니다.
• 모든 연산은 상자 개수(n)에 대해 O(1)의 시간 복잡도로 이루어지므로 전체 시간 복잡도는 O(n) 입니다.

---

구현 코드

function solution(order) {
  const stack = [];
  let answer = 0;
  let orderIndex = 0;
  const n = order.length;

  for (let i = 1; i <= n; i++) {
    if (i === order[orderIndex]) {
      answer++;
      orderIndex++;
      while (stack.length && stack[stack.length - 1] === order[orderIndex]) {
        stack.pop();
        answer++;
        orderIndex++;
      }
    } else {
      stack.push(i);
    }
  }

  return answer;
}