코딩테스트 스택 풀이: 크레인 인형뽑기 처리법

내가 푼 풀이

아래는 내가 처음 작성한 전체 코드입니다. 이후 단계별 설명에서는 이 코드를 기준으로 각 부분이 어떤 역할을 하는지 하나씩 살펴봅니다.

function solution(board, moves) {
  let arr = [];
  let answer = 0;
  let moveIndex = 0;

  for (let index of moves) {
    index--;
    while (moveIndex < board.length && board[moveIndex][index] === 0) {
      moveIndex++;
    }

    if (moveIndex < board.length && board[moveIndex][index] !== 0) {
      if (board[moveIndex][index] === arr.at(-1)) {
        answer += 2;
        arr.pop();
      } else {
        arr.push(board[moveIndex][index]);
      }
      board[moveIndex][index] = 0;
    }
    moveIndex = 0;
  }

  return answer;
}

먼저 내가 작성한 풀이는 문제를 있는 그대로 구현하는 방식에 가깝습니다. 크레인이 특정 열을 선택하면, 해당 열의 가장 위에서부터 인형을 하나 찾고, 그 인형을 바구니에 담는 흐름을 그대로 코드로 옮겼습니다.

이 풀이의 전체 흐름은 다음과 같이 나눌 수 있습니다.

1단계는 크레인이 이동한 열에서 집을 인형을 찾는 과정입니다. moves 배열의 각 값은 열 번호이므로, 1을 빼서 실제 인덱스로 변환한 뒤 위에서부터 탐색합니다.

for (let index of moves) {
  index--;
  while (moveIndex < board.length && board[moveIndex][index] === 0) {
    moveIndex++;
  }

이 코드는 선택된 열에서 값이 0이 아닌 지점을 찾을 때까지 위에서 아래로 내려가는 역할을 합니다. 즉, 크레인이 집을 수 있는 가장 위 인형을 찾는 단계입니다.

2단계는 인형을 바구니에 담으면서 바로 이전 인형과 비교하는 과정입니다. 바구니 역할을 하는 arr 배열의 마지막 값과 현재 집은 인형을 비교합니다.

if (moveIndex < board.length && board[moveIndex][index] !== 0) {
  if (board[moveIndex][index] === arr.at(-1)) {
    answer += 2;
    arr.pop();
  } else {
    arr.push(board[moveIndex][index]);
  }
  board[moveIndex][index] = 0;
}

여기서 같은 인형이 연속으로 들어오는 경우를 직접 처리합니다. 같은 경우에는 바구니에서 이전 인형을 제거하고, 제거된 인형의 개수를 answer에 더합니다.

마지막으로 각 move가 끝날 때마다 moveIndex를 다시 0으로 초기화하여, 다음 열 탐색이 항상 위에서부터 시작되도록 합니다.

이 풀이는 문제를 정확히 해결할 수 있지만, 크레인의 동작과 바구니의 상태를 모두 직접 관리해야 하기 때문에 코드 흐름이 다소 길어지고 복잡해지는 특징이 있습니다.

정답 풀이

다음은 같은 바구니 스택을 사용하면서 열 탐색을 for 반복문과 break로 정리한 풀이입니다. 문제 원문이 특정 정답 구현을 제공했다고 가정하지 않고 두 코드의 동작을 비교합니다.

function solution(board, moves) {
  let answer = 0;
  let stack = [];

  moves.forEach(pos => {
    for (let i = 0; i < board.length; i++) {
      if (board[i][pos - 1] !== 0) {
        let tmp = board[i][pos - 1];
        board[i][pos - 1] = 0;

        if (tmp === stack[stack.length - 1]) {
          stack.pop();
          answer += 2;
        } else {
          stack.push(tmp);
        }
        break;
      }
    }
  });

  return answer;
}

두 풀이의 바구니 처리에서 새 인형과 마지막 인형의 비교는 같습니다. 아래에서는 인형을 찾은 즉시 바구니를 갱신하고 해당 열 탐색을 끝내는 흐름을 확인합니다.

바구니에서는 항상 가장 마지막에 들어온 인형과 새로 들어온 인형을 비교합니다. 이 구조는 후입선출(LIFO) 특성을 가지는 스택과 완전히 동일합니다.

같은 스택의 상호작용 규칙은 JavaScript 올바른 괄호 스택 검증에서도 동일하게 확인할 수 있어, 스택 기반 사고를 비교하기 좋습니다.

첫 풀이의 arr도 push/pop/마지막 값 확인을 사용하는 스택입니다. 두 구현 모두 스택이며, 차이는 열 탐색의 while/for와 보조 인덱스 관리 방식입니다.

let answer = 0;
let stack = [];

이후 각 move에 대해 크레인이 집을 인형을 찾는 부분은 비교적 단순하게 처리합니다. 선택된 열을 위에서부터 순회하며 첫 번째 인형만 집습니다.

moves.forEach(pos => {
  for (let i = 0; i < board.length; i++) {
    if (board[i][pos - 1] !== 0) {
      let tmp = board[i][pos - 1];
      board[i][pos - 1] = 0;

인형을 집는 순간, 즉시 스택의 마지막 값과 비교합니다. 이때 조건 분기는 문제의 규칙과 1:1로 대응됩니다.

if (tmp === stack[stack.length - 1]) {
  stack.pop();
  answer += 2;
} else {
  stack.push(tmp);
}

같은 인형이면 제거하고 점수를 올리고, 다른 인형이면 그대로 스택에 쌓습니다. 이 과정이 반복되면서 바구니의 상태가 자연스럽게 유지됩니다.

JS 쇠막대기 스택 레이저 절단과 함께 읽으며 pop의 의미를 비교하세요. 이 문제는 같은 인형을 제거하지만 쇠막대기 문제는 레이저나 막대 끝의 닫는 괄호를 처리하므로, 제거 조건과 누적값은 다릅니다.

스택은 바구니의 마지막 인형을 찾는 데 쓰입니다. 선택한 열에서 인형을 찾기, 원래 칸을 0으로 바꾸기, 제거 개수를 갱신하기는 여전히 별도 로직으로 처리합니다.

내 풀이와 정답 풀이의 차이점

두 구현의 차이는 바구니 자료구조가 아니라 선택한 열을 탐색하고 탐색을 멈추는 방식입니다.

첫 구현은 while과 moveIndex를 쓰고 매 이동 뒤 인덱스를 초기화합니다. 둘째 구현은 이동마다 for를 새로 시작하고 인형 하나를 처리한 뒤 break합니다.

두 구현의 arr와 stack은 모두 바구니를 나타내며 LIFO 규칙을 따릅니다. 배열은 저장 수단이고 스택은 사용하는 규칙이므로 서로 대립하는 선택지가 아닙니다.

또한 내가 푼 풀이에서는 moveIndex와 같은 보조 변수를 사용해 상태를 직접 관리해야 했지만, 정답 풀이는 반복문과 스택만으로 흐름이 자연스럽게 이어집니다. 이는 코드의 가독성과 유지보수 측면에서도 큰 차이를 만듭니다.

코딩 테스트에서는 정답 여부뿐만 아니라, 문제를 얼마나 구조적으로 이해했는지도 함께 평가됩니다. 같은 문제를 풀더라도, 문제의 핵심 개념을 정확히 짚어낸 풀이가 더 좋은 코드로 평가받게 됩니다.

결론

크레인 인형뽑기 문제는 구현 문제처럼 보이지만, 실제로는 스택의 개념을 정확히 이해하고 있는지를 묻는 문제입니다. 문제의 규칙을 그대로 자료구조로 옮길 수 있을 때, 코드도 자연스럽고 간결해집니다.