64061. 크레인 인형뽑기 게임

프로그래머스 64061번 풀이

이 글은 Obsidian에서 마이그레이션되었으며, 그 과정에서 AI의 도움을 받았습니다. 오류나 누락된 내용이 있다면 댓글로 알려주세요!

문제

코딩테스트 연습 - 크레인 인형뽑기 게임 | 프로그래머스 스쿨

풀이

아이디어

우선 board를 사용하기 쉬운 자료 구조로 바꿔줬다. 크레인은 각 열의 맨 위 인형만 집을 수 있기 때문에 각 열을 개별 스택으로 관리하면 인형을 꺼내는 작업을 O(1)에 처리할 수 있다.

const boardStack = Array.from({ length: board.length }, () => new Array());
board.reverse().forEach((row) => {
  for (let idx = 0; idx < row.length; idx++) {
    row[idx] && boardStack[idx].push(row[idx]);
  }
});

그 다음에는 moves를 순회하며 인형을 뽑아준다. moves에서 각 위치에서 인형을 꺼내고 (pop) basket의 맨 위 인형과 같으면 터뜨려주면 된다. (주의 : 구해야 하는 것은 터지는 횟수가 아닌 터지는 인형의 개수이므로 터질 때 마다 정답이 2씩 늘어나야 한다.)

const basket = [];
let answer = 0;
for (let idx = 0; idx < moves.length; idx++) {
  const target = boardStack[moves[idx] - 1].pop();
  if (!target) continue;
  if (basket.length > 0 && target === basket[basket.length - 1]) {
    basket.pop();
    answer += 2;
  } else {
    basket.push(target);
  }
}

board를 좀 더 효율적으로 다루는 방법: 인형을 뽑을 때마다 pop해서 board 데이터를 직접 변경하는 방법도 있지만, top index만 저장해서 top index를 증가시켜주는 방식으로 pop과 비슷한 효과를 낼 수도 있다.