[Javascript][Programmers] 크레인 인형뽑기 게임

 

문제

• 쌓여있다 → 스택

 

나의 풀이

function solution(board, moves) {
    let answer = 0;
    const size = board.length;
    const basket = [];
    let picked = -1;

    for(const move of moves) {
        for(let i = 0; i < size; i++) {
            if(board[i][move - 1] === 0) continue;
            else {
                picked = board[i][move - 1];
                board[i][move - 1] = 0;
                if(basket[basket.length - 1] === picked) {
                    basket.pop();
                    answer = answer += 2;
                } else {
                    basket.push(picked);
                }
                break;
            }
        }
    }

    return answer;
}

각 동작마다 보드의 해당 열을 위에서부터 순차적으로 탐색해 인형을 찾고, 찾은 인형을 바구니(basket)에 넣습니다. 만약 바구니의 마지막 인형과 새로 넣을 인형이 같으면 바구니에서 제거하고, 제거된 인형의 개수를 answer에 2씩 더합니다.

 

문제점

• 보드의 해당 열을 위에서부터 순차적으로 탐색하는 과정이 중복해서 발생 → 보드를 스택으로 구현하면 해결 가능

 

다른 풀이

function solution(board, moves) {
  // ➊ 각 열에 대한 스택을 생성합니다. [[], [], [], [], []]
  const lanes = [...new Array(board[0].length)].map(() => []);

  // ➋ board를 역순으로 탐색하며, 각 열의 인형을 lanes에 추가합니다.
  for (let i = board.length - 1; i >= 0; i--) {
    for (let j = 0; j < board[0].length; j++) {
      if (board[i][j]) {
        lanes[j].push(board[i][j]);
      }
    }
  }

  // ➌ 인형을 담을 bucket을 생성합니다.
  const bucket = [];

  // ➍ 사라진 인형의 총 개수를 저장할 변수를 초기화합니다.
  let answer = 0;

  // ➎ moves를 순회하며, 각 열에서 인형을 뽑아 bucket에 추가합니다.
  for (const m of moves) {
    if (lanes[m - 1].length > 0) {
      // 해당 열에 인형이 있는 경우
      const doll = lanes[m - 1].pop();

      if (bucket.length > 0 && bucket[bucket.length - 1] === doll) {
        // ➏ 바구니에 인형이 있고, 가장 위에 있는 인형과 같은 경우
        bucket.pop();
        answer += 2;
      } else {
        // ➐ 바구니에 인형이 없거나, 가장 위에 있는 인형과 다른 경우
        bucket.push(doll);
      }
    }
  }

  return answer;
}

 

---

Reference

코딩테스트 합격자 되기: 자바스크립트 편