주요 포인트 한눈에 보기
카카오 기출로 자주 등장하는 크레인 인형뽑기 문제를 통해, 단순 구현과 스택 기반 사고의 차이를 정리합니다. 내가 작성한 코드와 정답 코드의 구조를 비교하며, 왜 스택이 핵심 자료구조인지 흐름 중심으로 설명합니다.
문제 설명
게임개발자인 죠르디는 크레인 인형뽑기 기계를 모바일 게임으로 만들려고 합니다.죠르디는 게임의 재미를 높이기 위해 화면 구성과 규칙을 다음과 같이 게임 로직에 반영하려고 합니다.
게임 화면은 1 x 1 크기의 칸들로 이루어진 N x N 크기의 정사각 격자이며 위쪽에는 크레인이 있고 오른쪽에는 바구니가 있습니다. (위 그림은 5 x 5 크기의 예시입니다). 각 격자 칸에는 다양한 인형이 들어 있으며 인형이 없는 칸은 빈칸입니다. 모든 인형은 1 x 1 크기의 격자 한 칸을 차지하며 격자의 가장 아래 칸부터 차곡차곡 쌓여 있습니다. 게임 사용자는 크레인을 좌우로 움직여서 멈춘 위치에서 가장 위에 있는 인형을 집어 올릴 수 있습니다. 집어 올린 인형은 바구니에 쌓이게 되는 데, 이때 바구니의 가장 아래 칸부터 인형이 순서대로 쌓이게 됩니다. 다음 그림은 [1번, 5번, 3번] 위치에서 순서대로 인형을 집어 올려 바구니에 담은 모습입니다.
만약 같은 모양의 인형 두 개가 바구니에 연속해서 쌓이게 되면 두 인형은 터뜨려지면서 바구니에서 사라지게 됩니다. 위 상태에서 이어서 [5번] 위치에서 인형을 집어 바구니에 쌓으면 같은 모양 인형 두 개가 없어집니다.
크레인 작동 시 인형이 집어지지 않는 경우는 없으나 만약 인형이 없는 곳에서 크레인을 작동시키는 경우에는 아무런 일도 일어나지 않습니다. 또한 바구니는 모든 인형이 들어갈 수 있을 만큼 충분히 크다고 가정합니다. (그림에서는 화면표시 제약으로 5칸만으로 표현하였음)
게임 화면의 격자의 상태가 담긴 2차원 배열 board와 인형을 집기 위해 크레인을 작동시킨 위치가 담긴 배열 moves가 매개변수로 주어질 때, 크레인을 모두 작동시킨 후 터트려져 사라진 인형의 개수를 return 하도록 solution 함수를 완성해주세요
[제한사항] board 배열은 2차원 배열로 크기는 5 x 5 이상 30 x 30 이하입니다. board의 각 칸에는 0 이상 100 이하인 정수가 담겨있습니다. 0은 빈 칸을 나타냅니다. 1 ~ 100의 각 숫자는 각기 다른 인형의 모양을 의미하며 같은 숫자는 같은 모양의 인형을 나타냅니다. moves 배열의 크기는 1 이상 1,000 이하입니다. moves 배열 각 원소들의 값은 1 이상이며 board 배열의 가로 크기 이하인 자연수입니다.
[[0,0,0,0,0],
[0,0,1,0,3],
[0,2,5,0,1],
[4,2,4,4,2],
[3,5,1,3,1]]
[1,5,3,5,1,2,1,4]내가 푼 풀이
아래는 내가 처음 작성한 전체 코드입니다. 이후 단계별 설명에서는 이 코드를 기준으로 각 부분이 어떤 역할을 하는지 하나씩 살펴봅니다.
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으로 초기화하여, 다음 열 탐색이 항상 위에서부터 시작되도록 합니다.
이 풀이는 문제를 정확히 해결할 수 있지만, 크레인의 동작과 바구니의 상태를 모두 직접 관리해야 하기 때문에 코드 흐름이 다소 길어지고 복잡해지는 특징이 있습니다.
정답 풀이
다음은 문제에서 제시된 정답 풀이의 전체 코드입니다. 이 코드는 바구니를 스택으로 모델링하여 문제의 규칙을 가장 자연스럽게 표현합니다.
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) 특성을 가지는 스택과 완전히 동일합니다.
정답 풀이는 이 점을 명확히 인식하고, 바구니를 스택으로 정의합니다.
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);
}같은 인형이면 제거하고 점수를 올리고, 다른 인형이면 그대로 스택에 쌓습니다. 이 과정이 반복되면서 바구니의 상태가 자연스럽게 유지됩니다.
이 풀이는 문제의 규칙을 자료구조에 그대로 위임했기 때문에, 별도의 상태 변수나 복잡한 조건 처리가 필요하지 않습니다.
내 풀이와 정답 풀이의 차이점
이제 두 풀이를 나란히 놓고 보면, 결과보다 더 중요한 차이점이 보입니다. 두 코드 모두 정답을 반환하지만, 문제를 바라보는 관점과 코드 구조에는 분명한 차이가 있습니다.
내 풀이와 정답 풀이의 차이점
두 풀이 모두 동일한 결과를 만들지만, 문제를 바라보는 관점에는 분명한 차이가 있습니다. 내가 푼 풀이는 문제의 조건을 하나씩 코드로 옮기는 방식이었다면, 정답 풀이는 문제의 구조 자체를 자료구조로 모델링한 방식입니다.
특히 바구니를 어떻게 해석하느냐에서 차이가 발생합니다. 바구니는 단순히 인형을 담는 배열이 아니라, 가장 마지막에 들어온 인형과의 비교가 반복적으로 발생하는 공간입니다. 이 특성은 스택의 LIFO 구조와 정확히 일치합니다.
또한 내가 푼 풀이에서는 moveIndex와 같은 보조 변수를 사용해 상태를 직접 관리해야 했지만, 정답 풀이는 반복문과 스택만으로 흐름이 자연스럽게 이어집니다. 이는 코드의 가독성과 유지보수 측면에서도 큰 차이를 만듭니다.
코딩 테스트에서는 정답 여부뿐만 아니라, 문제를 얼마나 구조적으로 이해했는지도 함께 평가됩니다. 같은 문제를 풀더라도, 문제의 핵심 개념을 정확히 짚어낸 풀이가 더 좋은 코드로 평가받게 됩니다.
결론
크레인 인형뽑기 문제는 구현 문제처럼 보이지만, 실제로는 스택의 개념을 정확히 이해하고 있는지를 묻는 문제입니다. 문제의 규칙을 그대로 자료구조로 옮길 수 있을 때, 코드도 자연스럽고 간결해집니다.
FAQ
Q. 왜 배열이 아니라 스택을 사용해야 하나요?
바구니의 맨 위 인형과 새로 들어온 인형을 비교해야 하기 때문에, 마지막 상태를 바로 확인할 수 있는 스택 구조가 적합합니다.
Q. board 배열을 직접 수정해도 괜찮나요?
문제 조건상 인형이 사라진 자리를 0으로 처리해야 하므로, board를 직접 수정하는 방식이 오히려 직관적입니다.