[JAVA] 크레인 인형뽑기 - Stack

한번만에 뽑아본 적이 없어요..

https://programmers.co.kr/learn/courses/30/lessons/64061?language=java

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

2019 카카오 개발자 겨울 인턴십 문제입니다.

 

생각과정

- 바구니는 스택으로 구현

- 크레인은 이차원 배열로 나타낸다.

- 크레인을 뒤집어서 배열로 구현하기 쉽게 만들자.

 주어진 크레인 배열은 x축이 크레인 바닥이다.

 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

ㅡㅡㅡㅡㅡ

move 배열이 크레인이 내려갈 column을 정하니까 계산하기 좋게 크레인을 왼쪽으로 눕힌다.

  0 0 0 4 3  |

  0 0 2 2 5  |

  0 1 5 4 1  |

  0 0 0 4 3  |

  0 3 1 2 1  |

이렇게 하면 move가 1일 때, 1번 row만 탐색해서 인형을 뽑으면 된다!

 

- 뽑은 인형 자리는 0으로!

 

구현

class Solution {
    public int solution(int[][] board_origin, int[] moves) {
        int answer = 0;
        int[][] board = new int[board_origin.length][board_origin[0].length];
        //바구니 선언
        int[] bucket = new int[board.length * board[0].length];
        int bucketTop = 0;
        int item;
        //계산하기 좋게 바꾸기!
        for(int i=0;i<board.length;i++){
            for(int j=0;j<board[i].length;j++){
                board[board[i].length-i-1][j] = board_origin[j][board[i].length-i-1];
            }
        }

        for(int i=0; i<moves.length; i++){
            //순서대로 크레인 움직이기
            for(int j=0;j<board[moves[i]-1].length;j++){
                //1. 인형 집기
                if((item = board[moves[i]-1][j]) != 0){
                    System.out.println(moves[i]);
                    //2. 바구니 맨 위의 인형과 비교
                    if(bucketTop == 0){
                        //바구니가 비었을 경우
                        bucket[bucketTop++] = item;
                    }else{
                        //터뜨릴 수 있는지 확인
                        if(bucket[bucketTop-1] == item){
                            //터뜨리기
                            bucketTop--;
                            answer += 2;
                        }
                        else{
                            //쌓기
                            bucket[bucketTop++] = item;
                        }
                    }
                    //비우기
                    board[moves[i]-1][j] = 0;
                    
                    //집었으면 종료
                    break;
                }
            }
        }
        
        return answer;
    }
    
}

 

결과

통과!