계산대 스택으로 만들 수 있는 순서

자바스크립트 코딩테스트 문제로 stack-sequence-validation 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.

today medium stack-sequence-validation 함수명: validateCheckoutStackOrder 제한 시간: 300ms

번호표 1번부터 n번까지가 차례대로 들어오고, 계산대 뒤에는 임시로 번호표를 쌓아 둘 수 있는 스택이 하나 있습니다.

문제 설명

번호표는 반드시 1, 2, 3, ..., n 순서로만 스택에 넣을 수 있습니다.

스택의 맨 위 번호표는 언제든지 꺼내서 출고 순서에 추가할 수 있습니다. 이때 주어진 배열 target과 정확히 같은 출고 순서를 만들 수 있으면 true, 만들 수 없으면 false를 반환하는 validateCheckoutStackOrder 함수를 작성하세요.

예를 들어 n = 5, target = [2, 1, 5, 4, 3]이라면 1을 넣고, 2를 넣은 뒤 2, 1을 꺼낼 수 있습니다. 이후 3, 4, 5를 넣고 5, 4, 3을 꺼내면 목표 순서를 만들 수 있습니다.

제한사항

1 <= n <= 100000
target.length === n
target의 각 원소는 정수입니다.
각 번호표는 한 번만 들어오고, 스택에서 한 번만 꺼낼 수 있습니다.
target에 중복 번호나 1부터 n 범위를 벗어난 번호가 있으면 만들 수 없는 순서입니다.
반환값은 목표 출고 순서를 만들 수 있는지 나타내는 boolean입니다.

예시

입력: n = 5, target = [2, 1, 5, 4, 3] -> 출력: true
입력: n = 5, target = [3, 1, 2, 5, 4] -> 출력: false
입력: n = 4, target = [1, 2, 3, 4] -> 출력: true
입력: n = 4, target = [2, 2, 3, 4] -> 출력: false

힌트

목표 순서의 다음 번호가 나올 때까지 새 번호표를 스택에 넣어 보세요.
스택 맨 위가 목표 번호와 같아지는 순간에는 바로 꺼낼 수 있습니다.
모든 번호를 넣었는데도 다음 목표 번호가 스택 맨 위에 없다면 그 순서는 만들 수 없습니다.

해설

핵심은 실제 과정을 그대로 따라가되, 가능한 pop은 미루지 않는 것입니다.

targetIndex를 아직 만들어야 할 목표 순서의 위치라고 둡니다. 번호표 1부터 n까지를 순서대로 스택에 넣고, 넣을 때마다 스택의 맨 위가 target[targetIndex]와 같으면 계속 꺼냅니다.

for (let number = 1; number <= n; number++) {
  stack.push(number);

  while (stack.length > 0 && stack[stack.length - 1] === target[targetIndex]) {
    stack.pop();
    targetIndex++;
  }
}

이 과정이 끝났을 때 targetIndex === n이면 목표 순서를 모두 만들었다는 뜻입니다.

반대로 어떤 목표 번호를 만들 수 없다면, 그 번호는 이미 스택의 아래쪽에 깔렸거나 아예 잘못된 값입니다. 스택은 맨 위에서만 꺼낼 수 있으므로 아래에 깔린 번호를 먼저 꺼낼 방법이 없습니다.

예를 들어 target = [3, 1, 2, 5, 4]를 보겠습니다.

1, 2, 3을 넣고 3을 꺼냅니다.
다음 목표는 1이지만 스택 맨 위는 2입니다.
2를 먼저 꺼내지 않고는 1을 꺼낼 수 없으므로 이 순서는 불가능합니다.

중복이나 범위 밖 번호도 자연스럽게 실패해야 합니다. 예를 들어 [2, 2, 3, 4]는 두 번째 2를 다시 꺼낼 수 없기 때문에 끝까지 매칭되지 않습니다.

시간 복잡도는 각 번호가 스택에 한 번 들어가고 한 번 나오므로 O(n)입니다. 공간 복잡도는 스택에 최대 n개가 쌓일 수 있어 O(n)입니다.

코드 작성

starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.

JavaScript 에디터 로딩 중...

커스텀 테스트

함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]

아직 실행하지 않았습니다.

실행 결과