🔗 링크

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

🧸 문제

크레인을 작동하면 해당 라인의 가장 상위에 있는 인형이 무조건 뽑히고, (만약 해당 라인에 인형이 하나도 없으면 아무것도 뽑지 않는다)

인형은 바구니에 담는다. 이 때 인형이 연속으로 2개 있으면 터져서 사라진다.

뽑기판 board이 주어지고 뽑는 라인의 순서인 moves이 주어질 때,

터져서 사라진 인형의 갯수를 구해야한다.

👀 예제로 문제 파악하기

입력 : 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]

뽑기판은 가로로 위부터 아래로 내려온다.

뽑기판을 그림으로 표현하면 위와 같이 된다.

moves 순서대로 크레인을 내려가서 뽑으면 3번째와 4번째가 1로 똑같기 때문에 사라진다.

그 후에 마지막에 있는 3과 5째로 내려오는3과 똑같기 때문에 사라진다.

총 사라지는 인형 수는 4개이다.

😮 알고리즘 풀이 순서

1. 바구니 역할을 해줄 stack을 준비하고, 0을 넣는다.
   • 0을 넣는 이유는 stack의 맨 위 값과 비교해야하는데 아무것도 없으면 오류가 나기 때문이다.
2. moves의 길이만큼 for문을 돌린다.
   • board의 길이만큼 for문을 돌린다. (해당 라인에서 인형을 뽑기 위해)
     • 만약 board[j][move - 1]이 0이라면 인형이 없는 것이기 때문에 넘어간다.
     • 0이 아니라면
       • Stack(바구니)의 가장 윗 요소와 board[j][move - 1]가 같은지 비교한다.
         • 같다면 인형이 터지는 것이기 때문에 Stack에 pop을 하고 answer에 2를 더한다.
         • 다르다면 Stack에 board[j][move - 1]를 push한다.
3. answer를 리턴한다.

👨‍💻 코드

public class Solution {
  public int solution(int[][] board, int[] moves) {
    int answer = 0;

    Stack<Integer> stack = new Stack<>();
    stack.push(0);

    for (int move : moves) {
      for (int j = 0; j < board.length; j++) {
        if (board[j][move - 1] != 0) {
          if (stack.peek() == board[j][move - 1]) {
            stack.pop();
            answer += 2;
          } else {
           stack.push(board[j][move - 1]);
          }
          board[j][move - 1] = 0;
          break;
        }
      }
    }
    return answer;
  }

  @Test
  public void 정답(){
    Assert.assertEquals(4, solution(new int[][]{{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}}, new int[]{1,5,3,5,1,2,1,4}));
    Assert.assertEquals(8, solution(new int[][]{{3,3,3,3,3},{3,3,3,3,3},{3,3,3,3,3},{3,3,3,3,3},{3,3,3,3,3}}, new int[]{1,5,3,5,1,2,1,4}));
    Assert.assertEquals(0, solution(new int[][]{{0,0,0,0,0},{0,0,0,0,0},{0,0,0,0,0},{0,0,0,0,0},{0,0,0,0,0}}, new int[]{1,5,3,5,1,2,1,4}));

  }
}