👿 문제

문제 설명

...
게임 화면의 격자의 상태가 담긴 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 배열의 가로 크기 이하인 자연수입니다.

• 크레인 인형뽑기 게임

🔍 접근 방법

첫 번째 시도

보자마자 일단 어려운 문제구나 싶었지만🥲 문제를 읽을 수록 구현할 기능만 정리 잘 하면 되겠구나 싶었다. 효율적인 방식은 그 이후에 고민하기로 하하.. 2차원 배열을 탐색해야하며, 재귀함수를 통해 지금 탐색부분의 값이 없다면 더 깊에 탐색해 들어가야한다.
일단 첫 번째 인상에서 필요한 기능은 다음과 같다.

1. 카운트 할 변수를 생성한다.
2. 크레인이 move크기만큼 인형을 뽑는다.
   1. 바구니(2차원 배열)에서 정해진 move 배열에 있는 수를 위(0)에서부터 탐색한다.
   2. 값이 0이라면 다음 배열에서 탐색한다.
   3. 값이 0이 아니라면 뽑은 인형 int를 반환한다.
   4. 만약 끝까지 탐색했는데 모두 0이라면 0을 반환한다.
3. 뽑은 인형이 0이 아니라면 작은 바구니(int[])에 담는다.
   1. 만약 바구니에 있는 마지막 값과 넣는 값이 같다면 둘다 터져서 없어진다.
      • 터진 갯수 카운트
   2. 만약 같지 않다면 배열에 쌓인다.
4. 카운트를 출력한다.

의사 코드

• 인형 뽑기 메서드

public int 인형뽑기(int[][] board, int move, int deep) {
	탐색할 것 = board[deep][move];
	if (0이 아니라면) {
    	해당 값을 뽑는다.
        그 자리는 0이 된다.
    }
    if (0이고 최대 깊이라면) {
    	return 0
    }
    if (0이라면) {
    	인형뽑기(더 깊이 가자);
    }
    return 인형
}

• 인형 담기 메서드

// 인형이 0이 아니라면 실행한다.
public Stack<Integer> 인형담기(Stack<integer> 바구니, int 인형) {
	if (바구니 제일 위에 있는 것 == 인형) {
    	// 바구니에서 빼버린다.
        바구니.pop()
    }
    if (바구니 제일 위에 있는 것 != 인형) {
    	// 바구니에 넣는다.
        바구니.push()
    }
    return 바구니
}

• 메인

class Solution {
    public int solution(int[][] board, int[] moves) {
    	// 변수 선언
    
    	for (move만큼 돌기) {
        	인형뽑기();
            if(인형이 0이 아니라면) {
            	인형담기();
            }
        }
    	
        int answer = 담겨있는 인형 배열 길이;
        return answer;
    }
}

첫 번째 시도 결과

import java.util.*;

class Solution {
    public int solution(int[][] board, int[] moves) {
        Stack<Integer> basket = new Stack<Integer>();
        int count = 0;
        
        for (int move : moves) {
            int doll = getDoll(board, move-1, 0);
            if (doll != 0) {
                putDoll(basket, doll, count);
            }
        }
        
        int answer = count;
        
        return answer;
    }
    
    public static int getDoll(int[][] board, int move, int deep) {
        int search=0;
        while (search==0) {
            search = board[deep][move];
            if (search!=0) {
                board[deep][move] = 0;
                break;
            } else if (search==0 && deep==board.length-1) {
                break;
            } else if (search==0) {
                deep ++;
            }
        }
        return search;
    }
    
    public static void putDoll(Stack<Integer> basket, int doll, int count) {
        if (basket.peek()==doll) {
            basket.pop();
            count++;
        }
        if (basket.peek()!=doll) {
            basket.add(doll);
        }
    }
}

위 코드는 에러가 났는데, 맨 처음 바구니가 비었을 때를 처리하지 못했기 때문이다.

Exception in thread "main" java.util.EmptyStackException
	at java.base/java.util.Stack.peek(Stack.java:101)
	at Solution.putDoll(Unknown Source)
	at Solution.solution(Unknown Source)
	at SolutionTest.lambda$main$0(Unknown Source)
	at SolutionTest$SolutionRunner.run(Unknown Source)
	at SolutionTest.main(Unknown Source)

결국은 IDE에서 디버깅해가면서 알아냈다. 아직 내 실력으로는 IDE 없이는 디버깅 하기 힘든 것 같다. 거기다 중간중간 자잘하게 잘못된 값을 출력하는 등의 오류가 있었다.
심지어 중간에 문제를 잘 못 읽은 것을 깨달아서 (터진 횟수가 아니라 터진 갯수를 출력하는 문제였다.) 추가 삽질을 더해야 했다.

💪 제출 결과

import java.util.*;

class Solution {
        public static int solution(int[][] board, int[] moves) {
        Stack<Integer> basket = new Stack<>();
        int count = 0;

        for (int move : moves) {
            int doll = getDoll(board, move-1, 0);
            if (doll != 0) {
                count = putDoll(basket, doll, count);
            }
        }

        return count;
    }

    public static int getDoll(int[][] board, int move, int deep) {
        int search=0;
        while (search==0) {
            search = board[deep][move];
            if (search!=0) {
                board[deep][move] = 0;
                break;
            } else if (search==0 && deep==board.length-1) {
                break;
            } else if (search==0) {
                deep ++;
            }
        }
        return search;
    }

    public static int putDoll(Stack<Integer> basket, int doll, int count) {
        if (basket.isEmpty()) {
            basket.push(doll);
        } else if (basket.peek()==doll) {
            basket.pop();
            count += 2;
        } else if (basket.peek()!=doll) {
            basket.add(doll);
        }
        return count;
    }
}

테스트 1 〉	통과 (0.13ms, 71.1MB)
테스트 2 〉	통과 (0.20ms, 74.2MB)
테스트 3 〉	통과 (0.15ms, 72.9MB)
테스트 4 〉	통과 (1.44ms, 74.6MB)
테스트 5 〉	통과 (0.14ms, 71MB)
테스트 6 〉	통과 (0.19ms, 73.9MB)
테스트 7 〉	통과 (0.23ms, 65.8MB)
테스트 8 〉	통과 (0.59ms, 77.8MB)
테스트 9 〉	통과 (0.46ms, 73.7MB)
테스트 10 〉	통과 (0.77ms, 79.7MB)
테스트 11 〉	통과 (1.01ms, 74.3MB)

---