[프로그래머스/Lv.1] 크레인 인형뽑기 (Java)

크레인 인형뽑기

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

---

풀이

해당 열에서 위에서부터 인형 찾기

• `moves`: 크레인이 이동하는 열 번호
• `col = m - 1` => 0-based 인덱스로 변환

 

`board[row][col] != 0`: 인형 발견 

• `borad[row][col] = 0`: 인형 뽑기
• 바구니 맨 위 인형
  • 같음 -> 2개 사라짐: `stack.poll()`, `cnt += 2`
  • 다름 -> `stack.push(doll)`

---

예시

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]]

 

col:  1  2  3  4  5

-------------------

row0 | 0  0  0  0  0

row1 | 0  0  1  0  3

row2 | 0  2  5  0  1

row3 | 4  2  4  4  2

row4 | 3  5  1  3  1

 

moves = [1, 5, 3, 5, 1, 2, 1, 4]

-> 실제 움직임: moves[i] - 1

---

코드

import java.util.*;

class Solution {
    public int solution(int[][] board, int[] moves) {
        Stack<Integer> stack = new Stack<>();
        int n = board.length;
        int cnt = 0;
        
        for (int m : moves) {
            int col = m - 1;
            
            for (int row = 0; row < n; row++) {
                if (board[row][col] != 0) {
                    int doll = board[row][col];
                    board[row][col] = 0;
                    
                    if (!stack.isEmpty() && stack.peek() == doll) {
                        stack.pop();
                        cnt += 2;
                    } else stack.push(doll);
                    break;
                }
            }
        }
        
        return cnt;
    }
}