[알고리즘 JS] 크레인 인형뽑기 게임 (프로그래머스 Lv.1)

문제

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

프로그래머스

풀이

/*

[풀이 해설]

1. N * N의 행렬이 존재할 때, moves로 받고있는 '크레인의 위치' 는 i번째 행의 인덱스가 된다.

2. 크레인의 위치에서 맨 위부터 시작해 인형이 존재할 때 까지 아래로 파고들기 때문에,
... 전체 board를 반복해서, board[i][move - 1] 로 접근해야한다. 
... moves로 들어오는 각 값을 0번째부터 시작하는 배열의 인덱스로 접근하기 위해서 -1을 해준다.

3. 크게 두 가지 경우로 분기할 수 있다. board[i][move - 1] 이 존재하느냐, 존재하지 않느냐.
... 존재하지 않는다면, 존재하는 i번째 행에 도달할 때 까지 board의 i로 반복을 진행한다.

4. 값이 존재한다면, 즉 인형을 찾았다면 board[i][move - 1]은 꺼내었다는 표시로 0으로 초기화한다. 
... 값이 존재할 때에도 두 가지 경우로 분기할 수 있다. 
... 바구니(스택)에 지금 넣을 인형과 같은 인형이 존재하느냐, 존재하지 않느냐.

5 - 1. 존재하지 않는 경우, stack에 인형 값을 바로 추가해주면 된다.
5 - 2. 존재하는 경우, stack.pop()을 한 뒤에 카운트를 2번 추가한다. 
... (사라지는 인형의 갯수를 세어야하기 때문에.)

*/

const 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],
];
const moves = [1, 5, 3, 5, 1, 2, 1, 4];

function solution1(board, moves) {
  // 인형을 담을 바구니 배열과 카운트 변수 선언
  const bascket = [];
  let count = 0;

  // moves 배열을 pos 로 하나씩 반복한다.
  for (let pos of moves) {
    // board 의 각 행을 i로 반복한다.
    for (let i = 0; i < board.length; i++) {
      // 해당 칸에 인형이 존재할 때 target에 임시로 저장하고, 해당 자리를 0으로 초기화
      if (board[i][pos - 1]) {
        let target = board[i][pos - 1];
        board[i][pos - 1] = 0;
        // 바구니의 마지막 요소가 뽑으려는 인형이랑 같으면
        if (bascket[bascket.length - 1] === target) {
          // 바구니에서 마지막 요소를 뺀다음 카운트를 올린다.
          bascket.pop();
          count += 2;
        }
        // 뽑으려는 인형이랑 마지막 요소가 다르다면 바구니에 넣는다.
        else {
          bascket.push(target);
        }
        break;
      }
      // 인형이 존재하지 않으면 다음 행으로 넘어감.
      else {
        continue;
      }
    }
  }
  return count;
}

const result1 = solution1(board, moves);
console.log(result1);

• 인형이 담기는 바구니가 스택이라고 생각하면 이해하기 쉬운 문제이다. 중첩 배열을 접근하는 조건이 살짝 까다로울 수 있는데 잘 생각해보면 조건별로 분기해서 풀 수 있다.