FrontEnd
Javascript
Diary
ML
CS
Django
Algorithm
AWS
Co-Work
HTML
CSS
Python
React
ReactNative

#56 알고리즘 연습 - 크레인 인형뽑기 게임 (Python & JS)

크레인 작동 시 인형이 집어지지 않는 경우는 없으나 만약 인형이 없는 곳에서 크레인을 작동시키는 경우에는 아무런 일도 일어나지 않습니다. 또한 바구니는 모든 인형이 들어갈 수 있을 만큼 충분히 크다고 가정합니다. (그림에서는 화면표시 제약으로 5칸만으로 표현하였음)

게임 화면의 격자의 상태가 담긴 2차원 배열 board와 인형을 집기 위해 크레인을 작동시킨 위치가 담긴 배열 moves가 매개변수로 주어질 때, 크레인을 모두 작동시킨 후 터트려져 사라진 인형의 개수를 return 하도록 solution 함수를 완성해주세요.

  • 제한사항
  • board 배열은 2차원 배열로 크기는 5 x 5 이상 30 x 30 이하입니다.
  • board의 각 칸에는 0 이상 100 이하인 정수가 담겨있습니다.
  • 0은 빈 칸을 나타냅니다.
  • 1 ~ 100의 각 숫자는 각기 다른 인형의 모양을 의미하며 같은 숫자는 같은 모양의 인형을 나타냅니다.
  • moves 배열의 크기는 1 이상 1,000 이하입니다.
  • moves 배열 각 원소들의 값은 1 이상이며 board 배열의 가로 크기 이하인 자연수입니다.
  • 입출력 예
board moves result
[[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]] [1,5,3,5,1,2,1,4] 4

입출력 예에 대한 설명

입출력 예 #1

인형의 처음 상태는 문제에 주어진 예시와 같습니다. 크레인이 [1, 5, 3, 5, 1, 2, 1, 4] 번 위치에서 차례대로 인형을 집어서 바구니에 옮겨 담은 후, 상태는 아래 그림과 같으며 바구니에 담는 과정에서 터트려져 사라진 인형은 4개 입니다.

문제풀이
board 가 2차원 배열로 주어져 있고 격자를 기준으로 본다면 첫번째 row를 시작으로 moves에서 제시하는 칸을 탐색해야한다. 그러면 board 리스트를 탐색하면서 moves가 가리키는 index의 값을 체크하면 되는데 moves의 list에 pop()메서드를 잘 사용하면 이중 for문을 벗어날 수 있을거라 생각했다. 하지만 그러기 위해서는 첫번쨰 index부터 차근차근탐색해야 하는 조건때문에 moves의 배열을 뒤집어줘야했고, if문으로 moves의 배열이 빈배열이 될때까지 돌려주는 반복 조건을 걸어주는 등 크게 효율적이지 않아 보였다. 따라서 2중 for문을 사용하되 break로 조금이나마 더 효율적으로 탐색하도록 했고, pick 한 인형을 쌓는 box에 대해서 같은 인형이 연속해서 있을경우 제거되므로, 나중에 다시 탐색하지 않기 위해서 넣을때 마지막 element가 같은지 체크해서 cnt를 해준다.


내 풀이 🏆

사람들이 많이 선택한 풀이와 맥락을 같이 하고있어서 추가적인 설명은 안해도 될것 같다.

def solution(board, moves):
    answer = 0
    stack_box = [0]
    for i in moves:
        for sub_list in board:
            doll = sub_list[i-1]
            if doll !=0:

                if stack_box[-1] == doll:
                    stack_box.pop()
                    answer += 2
                else:
                    stack_box.append(doll)

                sub_list[i-1] = 0
                break
    return answer
function solution(board, moves) {
    var answer = 0;
    var stack_box = [0];
    for (var i = 0; i < moves.length; i++) {
        for (var j = 0; j < board.length; j++) {
            if (board[j][moves[i] - 1] !== 0) {
                if (
                    stack_box[stack_box.length - 1] === board[j][moves[i] - 1]
                ) {
                    stack_box.pop();
                    answer += 2;
                } else {
                    stack_box.push(board[j][moves[i] - 1]);
                }
                board[j][moves[i] - 1] = 0;
                break;
            }
        }
    }
    return answer;
}
  • JS로 for문을 쓰다보니까 python과 달라 약간 미숙한 점이 보이는데 map을 이용해서 하나하나 탐색해주는 방식으로 변환해주면 좀더 index를 찾아가지 않고 더 직관적인 코드가 나올 수 있을 것 같다. 그리고 처음에 JS로 제출했을때 정확도가 실패했던 부분은 JS에서도 python과 마찬가지로 마지막 원소를 arr[-1]과 같이 indexing해줬는데 JS에서는 이와 같이 해줄수 없고 length -1의 방법으로 인덱싱을 해줘야 하는 것 때문에 안 되었었다.