JavaScript로 스택 푸시·팝 순서 유효성 검사하기

문제 정의

두 개의 배열 pushed와 popped를 각각 첫 번째, 두 번째 인자로 받는 JavaScript 함수를 작성해야 합니다. 두 배열의 모든 요소는 중복 없이 고유한 값으로만 구성되어 있다고 보장됩니다.

이 함수는 popped 배열이 처음에 비어 있던 스택에 대해 push(삽입)와 pop(삭제) 연산을 순서대로 수행한 결과로 나올 수 있는 경우에 한해서만 true를 반환하고, 그렇지 않다면 false를 반환해야 합니다.

입력 예시

const pushed = [1, 2, 3, 4, 5];
const popped = [4, 5, 3, 2, 1];

위 입력에 대한 출력은 다음과 같아야 합니다.

const output = true;

출력 설명

다음과 같은 연산 순서를 거치면 이 결과를 얻을 수 있습니다.

push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

즉, 1부터 4까지 차례대로 스택에 넣은 뒤 4를 꺼내고, 이어서 5를 넣었다가 꺼낸 후 나머지 요소들을 위에서부터 순서대로 제거하면 [4, 5, 3, 2, 1]이라는 pop 순서가 만들어집니다.

구현 코드

이 문제를 해결하는 전체 코드는 다음과 같습니다.

const pushed = [1, 2, 3, 4, 5];
const popped = [4, 5, 3, 2, 1];
const validateSequence = (pushed = [], popped = []) => {
   let pushedIndex = 0
   let poppedIndex = 0
   const stack = []
   while (pushedIndex < pushed.length) {
      if (stack[stack.length - 1] !== popped[poppedIndex]) {
         stack.push(pushed[pushedIndex++])
      } else {
         stack.pop()
         poppedIndex += 1
      }
   }
   while (stack.length) {
      if (stack.pop() !== popped[poppedIndex++]) {
         return false
      }
   }
   return true;
};
console.log(validateSequence(pushed, popped));

동작 원리

이 알고리즘의 핵심은 실제 스택을 직접 시뮬레이션하는 것입니다.

push 단계: 스택의 최상단(top) 요소가 popped 배열에서 현재 확인해야 할 값과 일치하지 않으면, pushed 배열의 다음 요소를 스택에 삽입합니다.
pop 단계: 스택 최상단이 기대하는 값과 일치하면 해당 요소를 꺼내고(pop), poppedIndex를 하나 증가시켜 다음 목표 값을 가리키도록 합니다.
최종 검증: 모든 push가 끝난 뒤 스택에 남아 있는 요소들을 차례로 pop하면서 popped 배열의 나머지 값들과 순서대로 일치하는지 확인합니다. 하나라도 어긋나면 false를 반환합니다.

모든 검증을 통과하면 주어진 순서가 실제로 가능한 연산 결과임을 의미하므로 true를 반환합니다. 이 알고리즘의 시간 복잡도는 각 요소가 최대 한 번씩 push되고 pop되므로 O(n), 추가로 사용하는 스택 공간 역시 최악의 경우 n개의 요소를 저장할 수 있어 O(n)입니다.

출력 결과

콘솔에 출력되는 결과는 다음과 같습니다.

true