[프로그래머스] 크레인 인형뽑기 게임 (JAVA)

링크

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

프로그래머스

 

문제 요약

N*N `board`에 여러 모양의 인형(1*1)이 쌓여있는 상태이고, 크레인은 각 줄의 가장 위에 있는 인형을 집어 올린다.

그리고 집어 올린 인형을 한 줄 바구니에 쌓아 올릴 때, 같은 모양의 인형이 연속해서 쌓이면 이 두 인형은 없어진다.

 

2차원 배열 `board`와 인형을 집기 위해 크레인을 작동시킨 위치가 담긴 배열 `moves`가 매개변수로 주어질 때, 크레인을 모두 작동시킨 후 사라진 인형의 개수를 반환하기

제한

• `board` 배열은 2차원 배열로 크기는 "5 x 5" 이상 "30 x 30" 이하입니다.
• `board`의 각 칸에는 0 이상 100 이하인 정수가 담겨있습니다.
  • 0은 빈칸을 나타냅니다.
  • 1 ~ 100의 각 숫자는 각기 다른 인형의 모양을 의미하며 같은 숫자는 같은 모양의 인형을 나타냅니다.
• `moves` 배열의 크기는 1 이상 1,000 이하입니다.
• `moves` 배열 각 원소들의 값은 1 이상이며 board 배열의 가로 크기 이하인 자연수입니다.

 

풀이

바구니는 인형을 집어넣고, 조건 만족 시 위에서부터 인형이 없어지기 때문에 스택 형태를 떠올릴 수 있습니다.

1. `moves`의 첫 번째 값을 가져옵니다.
2. `board`에서 해당 위치의 맨 위부터 인형이 담겨있는지 확인합니다.
   1. 만약 값이 0이라면, 빈칸이므로 한 칸 아래로 내려갑니다.
3. 만약 인형이 있는 위치만큼 내려왔으면, 인형을 뽑았다는 의미로 해당 위치를 빈칸(0)으로 표시합니다.
4. 현재 바구니의 맨 위 인형과 새로 뽑은 인형의 값이 같으면, 두 인형은 모두 사라집니다.
   1. 바구니의 맨 위 인형을 제외시키고, 사라진 인형의 개수를 2 감소시킨다.
5. `moves`에 담긴 모든 값에 대해 2~4 과정을 반복한다.

주의할 점은 `moves`에 들어있는 값은 인덱스가 아닙니다! 따라서 -1을 해줘서 0부터 시작하게 인덱싱 해줘야 합니다.

 

코드

import java.util.*;
class Solution {
    public int solution(int[][] board, int[] moves) {
        Stack<Integer> bucket = new Stack<>();
        int cnt=0;
        for(int i=0; i<moves.length; i++){
            for(int j=0; j<board.length; j++){
                int temp = board[j][moves[i]-1];
                if(temp!=0){
                    board[j][moves[i]-1] = 0;
                    if(!bucket.isEmpty() && bucket.peek()==temp){
                        bucket.pop();
                        cnt+=2;
                    } else{
                        bucket.push(temp);
                    }
                    break;
                }
            }
        }
        return cnt;
    }
}

🏷 시간 복잡도

• `M`: moves의 길이
• `N`: board의 가로 크기
• 이중 for문: `O(M*N)`
• 최종 시간 복잡도: `O(M*N)`

🏷 실행 속도

Time: 1.29 ms, Memory: 76.3 MB