programmers 크레인 인형뽑기 게임

https://programmers.co.kr/learn/courses/30/lessons/64061

코딩테스트 연습 - 크레인 인형뽑기 게임

 

 

문제 분석

- 게임 화면의 격자를 2차원 배열로 입력받는다.

- 인형을 집기 위해 크레인을 작동시킨 위치가 담긴 배열을 입력받는다.

- 작동시킬만큼 for문으로 처리한다.

- 크레인을 모두 작동시킨 이후 터트려 사라진 인형의 개수를 리턴한다.

- 처음에 크레인을 작동시켜 게임 화면 격자에 있는 인형의 종류를 스택(Stack)에 넣는다.

- 그 이후에 인형을 넣을 경우 스택에 마지막으로 들어간 인형과 추가될 인형을 비교한다.

- 비교하여 같을 경우 터뜨려 정답에 두 개의 인형을 처리하고, 같지 않을 경우 순서대로 다시 스택에 넣는다.

- 뽑은 인형이 있던 자리(게임 화면)는 0으로 처리해준다.

- 인형의 위치를 찾을 때는 해당 위치의 세로 길이만큼 판단하다가 0이 아닌 인형이 나타나는 경우를 찾아야 한다.

 

 

문제 풀이

1. for문을 통해서 전체 크레인을 작동해야하는 만큼 처리한다.

2. 세로의 길이만큼 탐색하면서 인형이 있는지 확인한다.

3. 뽑아야하는 인형이 있는 경우 해당 인형을 처음 뽑을 경우와 그 이후일 경우를 if문으로 나누어 처리한다.

4. 처음 인형을 뽑은 경우 그냥 스택에 넣어준다.

5. 기존에 인형이 있었을 경우 스택에 마지막으로 넣어준 인형과 비교하여 같을 경우 터뜨려서 정답에 개수를 추가하고, 같지 않을 경우 순서대로 다시 스택에 넣어준다.

6. 인형이 있던 게임 화면의 좌표에는 0으로 처리해준다.

7. 정답을 리턴한다.

import java.util.*;

class Solution {
    public int solution(int[][] board, int[] moves) {
        int answer = 0;
        
        Stack<Integer> stack = new Stack<>();
        
        for(int i=0;i<moves.length;i++){ // 전체 크레인을 작동시키는 만큼 처리
            for(int j=0;j<board.length;j++){ // 세로 길이만큼 탐색하면서 인형을 찾음
                if(board[j][moves[i]-1]!=0){ // 뽑아야할 인형이 있는 경우
                    if(stack.size()==0){ // 인형을 처음 뽑은 경우
                        stack.add(board[j][moves[i]-1]);
                    }else{ // 기존에 인형이 있는 경우
                        int doll = stack.pop();
                        if(doll!=board[j][moves[i]-1]){ // 인형이 같지 않다면 다시 두 개 다 넣어준다.
                            stack.add(doll);
                            stack.add(board[j][moves[i]-1]);
                        }else{
                            answer += 2;
                        }
                    }
                    board[j][moves[i]-1] = 0;
                    break;
                }
            }
        }
        
        return answer;
    }
}

 

 

https://github.com/SOEUN2/Algorithm