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

문제

택배상자

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

 

 

예시 코드

function solution(order) {
  const stack = [];
  let cur = 1;
  let cnt = 0;

  for (const box of order) {
    while (cur <= box) {
      stack.push(cur++);
    }

    if (stack.pop() !== box) return cnt;
    cnt++;
  }

  return cnt;
}

 

풀이

택배 기사님이 원하는 상자 순서를 나타내는 정수 배열 order가 주어졌을 때, 영재가 몇 개의 상자를 실을 수 있는지를 구하는 문제입니다.

 

보조 컨테이너 벨트는 LIFO 방식으로 작동하므로, 스택을 사용해서 구현합니다.

 

상자를 싣는 과정은 다음과 같습니다.

• 컨테이너 벨트에서 차례로 상자를 꺼내, 트럭에 실어야 하는 순서와 비교합니다.
  • 순서가 맞는 경우, 상자를 싣습니다.
  • 순서가 잘못된 경우, 상자를 보조 컨테이너에 보관합니다.
• 컨테이너 벨트에서 찾지 못한 경우, 보조 컨테이너의 마지막 상자를 꺼냅니다.
  • 현재 순서가 아닌 경우, 작업을 끝냅니다.

 

이를 코드로 나타내면 대략 이렇습니다.

for (const box of order) {
  let found = false;
  while (true) {
    if (cur < box) {
      stack.push(cur++);
    } else {
      cnt++;
      found = true;
      break;
    }
  }
  if (found) continue;

  if (stack.pop() !== box) return cnt;
  cnt++;
}

 

실제 구현한 코드는 기존 과정을 조금 변형하여 작성했습니다.

• 컨테이너 벨트에서 차례로 상자를 꺼내, 보조 컨테이너에 집어넣습니다.
  
  • 현재 순서인 상자가 나올 때까지 반복합니다.
• 보조 컨테이너의 마지막 상자를 꺼냅니다.
  • 현재 순서가 아닌 경우, 작업을 끝냅니다.