문제

프로그래머스 - 크레인 인형뽑기 게임

문제 풀이

가장 직관적입 방법은 moves를 순회하면서 board 배열에 깊이 0 부터 인형을 찾는 것.

다만 이런 과정은 $O(N)$의 과정이 인형을 뽑을 때 마다 발생한다는 생각이 들었다.

깊이를 관리하는 것도 귀찮게 느껴지기는 했고.

따라서 해당 탐색 시간을 미리 탐색을 해 둔 상태로 진행하기.

전처리

접근시간을 $O(1)$로 줄이기 위함

의사코드 : 각 줄 별로 별도의 배열을 만들어 쉽게 pop() 하자.

크레인 게임에서 특정 열의 가장 위 인형을 찾는 것은 스택의 pop()과 동일하다.

따라서 board 배열을 열 기준으로 재구성하여 인형을 밑에서 위로 쌓아올린 배열을 사용할 것이다. (boardByLineIdx)

시간 복잡도

\[O(N \times M)\]

보드 모든 칸을 한 번 순회하기 때문.

보드 크기가 $30 \times 30$ 인 경우에도 900번의 연산만 필요하다.

메인 로직

boardByLineIdx를 준비했으므로, moves 배열을 순회하며 인형을 뽑는 과정은 매우 빨라진다.

1. 인형 뽑기와 예외 처리

의사코드 : 해당 줄에 아무것도 없다면 넘겨버린다.

moves의 값은 1 부터 시작하므로 배열 인덱스 lineIdx = move - 1 로 변환하여 접근한다.

// ... 기타 코드
for (const move of moves) {
  const lineIdx = move - 1;

  if (boardByLineIdx[lineIdx].length === 0) {
    continue;
  }
  // O(1) 뽑기
  const curTarget = boardByLineIdx[lineIdx].pop();
}

2. 바구니 (Stack) 로직

의사코드 : 스택에 쌓기 전 판단하여 연쇄반응을 미리 배제하고, 성립되면 answer += 2

바구니 역시 stack으로 작동한다. 새로 뽑은 인형을 바구니에 넣기 전, 바구니 맨 위 인형과 비교한다

if (basket.length > 0 && basket[basket.length - 1] === curTarget) {
  basket.pop(); // O(1)
  answer += 2;
} else {
  basket.push(curTarget); // O(1)
}

이 길이는 moves 배열의 길이(L) 만큼 반복되며, 내부 연산은 모두 1 이므로, 시간복잡도는 $O(L)$

최종 시간 복잡도와 공간 복잡도

\[O(N^2 (보드의 크기) + L (움직임))\]

공간 복잡도 고민 (feat 함수)

새로운 배열을 만든 이유 : 시간 복잡도 이득이 있을 거라고 생각함. 또한 실제 코드를 쓰는게 간편해짐

단 이런 배열로 인해 $O(N \times M)$ 의 공간이 추가적으로 필요하다

정답 코드

function solution(board, moves) {
  let answer = 0;

  const boardLen = board.length;
  const lineLen = board[0].length;

  const boardByLineIdx = [];

  for (let line = 0; line < lineLen; line++) {
    const tmp = [];

    for (let depth = 0; depth < boardLen; depth++) {
      const curDoll = board[depth][line];
      if (curDoll !== 0) {
        tmp.push(curDoll);
      }
    }
    boardByLineIdx.push(tmp.reverse());
  }

  const basket = [];

  for (const move of moves) {
    const lineIdx = move - 1;

    // 인형이 없는 경우 아무 일 없음.
    if (boardByLineIdx[lineIdx].length <= 0) {
      continue;
    }

    const curTarget = boardByLineIdx[lineIdx].pop();

    if (basket.length > 0 && basket[basket.length - 1] === curTarget) {
      basket.pop();
      answer += 2;
    } else {
      basket.push(curTarget);
    }
  }

  return answer;
}

마무리 및 여담

문제를 풀며 공간복잡도와 시간 복잡도에 대해 한 번 다시 생각해보게 되었다.

또 문제를 풀고 이렇게 회고하면서 아 이렇게 하지 말걸 혹은 이건 이래서 마음에 들어! 라는 부분이 있었다.

~~변수명 진짜 어려움~~

남의 풀이도 보면서 시간/공간 복잡도를 생각할 수 있다면 더욱 좋은 코드를 작성할 수 있게 되지 않을까?

화이팅화이팅

-뱅-

[Node.js] 프로그래머스 - 크레인 인형뽑기 게임

공간 복잡도를 희생해 시간 복잡도를 벌어보자.

문제