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

프로그래머스 programmers Level1 크레인 인형 뽑기 게임 - java 자

[문제]

2019 카카오 개발자 겨울 인턴십

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

프로그래머스

 

[풀이]

가장 나중에 넣은 값을 확인 할 수 있는 LIFO 구조의 Stack 을 이용하자.

• 문제에 주어진 입출력 예제로 풀어보자.
  • board = [[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]]
  • moves = [1,5,3,5,1,2,1,4]
  • result = 4

예제의 board[][] 2차원 배열을 도식화하면 다음과 같다.

moves 는 숫자로 좌측부터 1, 2, 3, 4, 5 이지만, 배열의 인덱스로 하기위해 -1 을 해주어야 한다.

moves 의 순서대로 크레인이 인형을 뽑는 과정을 도식화하면 다음과 같다.

※ 참고 : moves 의 순서대로 얻는 board 값을 동일한색으로 표기했다.

1. 크레인이 움직이는 moves 를 for문으로 확인한다.
2. 배열 board[i] 의 (moves-1) 원소를 for문으로 확인한다.
   2.1. board[i][moves-1] 의 값이 0 이 아닌 경우, Stack 에 push() 한다.
   2.2. 아래의 조건에 해당하는 경우, Stack 에서 가장 위에있는 값을 pop() 하고 개수 +2 한다.
          조건
          Stack 이 공백이 아니면서, board[i][moves-1] 의 값과 현재 Stack 의 peek() 가장 위의 값이 동일하다.
   2.3. 크레인으로 인형을 꺼냈으므로 board[i][moves-1] 의 값을 0으로 바꿔준다. 3. 터트린 수를 리턴한다.

여기서 알아야 할 것은 배열을 확인하는 순서다.

moves = 1 이라면, 첫번째 원소만 순차적으로 확인해서 0 이 아닌 경우의 값을 취득해야 한다.

• board[0][0] = 0 ⇒ 0 번째 배열의 0번 원소
• board[1][0] = 0 ⇒ 1 번째 배열의 0번 원소
• board[2][0] = 0 ⇒ 2 번째 배열의 0번 원소
• board[3][0] = 4 ⇒ 3 번째 배열의 0번 원소

정리하면, board[ i ][moves - 1] 으로 i 를 1 씩 증가시키며 확인한다.

 

[java 코드]

import java.util.*;

/**
 * 크레인 인형 뽑기 게임
 * @param board 게임 화면 "1 x 1" 크기의 칸들로 이루어진 "N x N" 크기의 정사각 격자
 * @param moves 인형을 집기 위해 크레인을 작동시킨 위치가 담긴 배열
 * @return 크레인을 모두 작동시킨 후 터트려져 사라진 인형의 개수
 */
public int solution(int[][] board, int[] moves) {
    int answer = 0;
    // stack.peek() : top 데이터 취득
    Stack<Integer> stack = new Stack<>();
    for (int m : moves) {
       for (int i = 0; i < board.length; i++) {
          // 0이 아닌 값일때까지 찾아서
          if (board[i][m - 1] != 0) {
             // 집어넣는 값이 현재 스택의 맨 위 값과 동일하면 터트려야한다.
             if (!stack.empty() && board[i][m - 1] == stack.peek()) {
                stack.pop();
                answer += 2;
             } else {
                // 0이 아닐 때 값을 넣는다.
                stack.push(board[i][m - 1]);
             }
             // 값을 바구니에 넣고다면 board 에서 삭제
             board[i][m - 1] = 0;
             // 넣었으니 break
             break;
          }
       }
    }
    return answer;
}