카카오의 크레인 인형뽑기 문제를 풀어보았다.
1. 문제
문제는 다음과 같다.
게임 화면은 "1 x 1" 크기의 칸들로 이루어진 "N x N" 크기의 정사각 격자이며 위쪽에는 크레인이 있고 오른쪽에는 바구니가 있습니다.
각 격자 칸에는 다양한 인형이 들어 있으며 인형이 없는 칸은 빈칸입니다. 모든 인형은 "1 x 1" 크기의 격자 한 칸을 차지하며 격자의 가장 아래 칸부터 차곡차곡 쌓여 있습니다.
게임 사용자는 크레인을 좌우로 움직여서 멈춘 위치에서 가장 위에 있는 인형을 집어 올릴 수 있습니다. 집어 올린 인형은 바구니에 쌓이게 되는 데, 이때 바구니의 가장 아래 칸부터 인형이 순서대로 쌓이게 됩니다.
만약 같은 모양의 인형 두 개가 바구니에 연속해서 쌓이게 되면 두 인형은 터뜨려지면서 바구니에서 사라지게 됩니다.
크레인 작동 시 인형이 집어지지 않는 경우는 없으나 만약 인형이 없는 곳에서 크레인을 작동시키는 경우에는 아무런 일도 일어나지 않습니다. 또한 바구니는 모든 인형이 들어갈 수 있을 만큼 충분히 크다고 가정합니다.
게임 화면의 격자의 상태가 담긴 2차원 배열 board와 인형을 집기 위해 크레인을 작동시킨 위치가 담긴 배열 moves가 매개변수로 주어질 때, 크레인을 모두 작동시킨 후 터트려져 사라진 인형의 개수를 return 하도록 solution 함수를 완성해주세요.
대충 말하자면 인형을 뽑을건데 같은인형을 연속해서 뽑으면 해당인형2개가 없어진다는 이야기다.
따라서 구해야할 것은 몇개의 인형이 사라지는가이다.
2. 설계
1) Basic 설계
우선 moves배열을 보고 board배열에서 어떠한 값(변수 target)이 끄집어 나와지는지 알아야 했다.
그 후, 나온값(변수 target)을 stackArrayArrayList에 넣었다.
같은 인형을 연속해서 뽑을경우 인형이 사라지는것을 구현하기 위해
바로 직전에 뽑은 인형(변수 top)이 무엇인지 일아야했다.
target과 top이 같다면 stackArray의 마지막 인형을 없앴다.
(target은 아직 stackArray에 넣지 않았으므로 top만 제거함)
이후 2개가 제거 되었으므로 변수answer를 2 증가시켰다.
2) 예외처리
인형이 없는경우는 값'0'을 가져오므로 다음 행동을 할 수 있도록 처리하였다.
3. 구현
위의 설계를 구현하면 아래의 코드가 된다.
import java.util.*;
class Solution {
public int solution(int[][] board, int[] moves) {
int answer = 0;
// 쌓일 ArrayList
ArrayList<Integer> stackArray = new ArrayList<Integer>();
// 현재 움직이는 위치
int currentMove = 0;
// 현재 크레인이 뽑아올 값(인형)
int target = -1;
// 쌓인 ArrayList의 마지막 요소
int top = 0;
// 마지막 인덱스
int lastIdx = -1;
// 1. moves 위치의 아이템을 가져옴
// 2. stackArray에 쌓음
for(int i = 0; i < moves.length; i++){
currentMove = moves[i] -1;
// board에서 해당 값 가져오기
for(int j = 0; j < board.length; j++){
target = board[j][currentMove];
if(target != 0){
board[j][currentMove] = 0;
break;
}
}
// 가져온 값(인형)이 0인경우
if( target == 0){
continue;
}
// 쌓인 종류가 없다면 삽입함
if(stackArray.size() == 0){
stackArray.add(target);
continue;
}
// 마지막 인덱스 수집
lastIdx = stackArray.size() -1;
// 마지막 요소 가져오기
top = stackArray.get(lastIdx);
if ( target == top){
// 마지막 인덱스 삭제
stackArray.remove(lastIdx);
// 값 2개 증가시키기
answer+=2;
}else{
// 꺼낸 값을 stackArray에 넣기
stackArray.add(target);
}
target = -1;
}
return answer;
}
}4. 마무리
테스트의 1,2 번만 실패하여 코드를 보았지만 알 수 없었다.
테스트케이스의 테스트값들을 알고 싶었다.
'질문하기'의 질문내역들을 살펴보던중 값'0'이 삽입되고 있지 않은지 확인하라는 글을 읽고 코드를 수정하였다.
그 결과 테스트를 통과할 수 있었다.
문제를 꼼꼼히 읽는것도 중요하지만, 다시한번 리뷰하며 스스로 빼먹은 부분은 없는지 점검하는것도 필요하다고 생각되었다.
