문제

크레인 인형뽑기 게임

문제 설명

게임개발자인 "죠르디"는 크레인 인형뽑기 기계를 모바일 게임으로 만들려고 합니다.
"죠르디"는 게임의 재미를 높이기 위해 화면 구성과 규칙을 다음과 같이 게임 로직에 반영하려고 합니다.

게임 화면은 "$1 \times 1$" 크기의 칸들로 이루어진 "$N \times N$" 크기의 정사각 격자이며 위쪽에는 크레인이 있고 오른쪽에는 바구니가 있습니다. (위 그림은 "$5 \times 5$" 크기의 예시입니다.)
각 격자 칸에는 다양한 인형이 들어 있으며 인형이 없는 칸은 빈칸입니다.
모든 인형은 "$1 \times 1$" 크기의 격자 한 칸을 차지하며 격자의 가장 아래 칸부터 차곡차곡 쌓여 있습니다.
게임 사용자는 크레인을 좌우로 움직여서 멈춘 위치에서 가장 위에 있는 인형을 집어 올릴 수 있습니다.
집어 올린 인형은 바구니에 쌓이게 되는 데, 이때 바구니의 가장 아래 칸부터 인형이 순서대로 쌓이게 됩니다.
다음 그림은 [1번, 5번, 3번] 위치에서 순서대로 인형을 집어 올려 바구니에 담은 모습입니다.

만약 같은 모양의 인형 두 개가 바구니에 연속해서 쌓이게 되면 두 인형은 터뜨려지면서 바구니에서 사라지게 됩니다.
위 상태에서 이어서 [5번] 위치에서 인형을 집어 바구니에 쌓으면 같은 모양 인형 두 개가 없어집니다.

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

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

---

제한사항

• board 배열은 2차원 배열로 크기는 "$5 \times 5$" 이상 "$30 \times 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

---

문제 풀이

인형 뽑기 보드는 다음과 같이 존재함. (0은 빈 공간)

1	2	3	4	5
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번의 4번 인형을 뽑아 바구니에 넣습니다.

바구니
4

그럼 보드는 다음과 같습니다.

1	2	3	4	5
0	0	0	0	0
0	0	1	0	3
0	2	5	0	1
0	2	4	4	2
3	5	1	3	1

board[3][0]의 값을 0으로 변경하고 basket에 [4] 추가

두 번째 크레인은 5번의 3번 인형을 뽑아 바구니에 넣습니다.

바구니
3
4

그럼 보드는 다음과 같습니다.

1	2	3	4	5
0	0	0	0	0
0	0	1	0	0
0	2	5	0	1
0	2	4	4	2
3	5	1	3	1

board[1][4]의 값을 0으로 변경하고 basket에 [3] 추가

세 번째 크레인은 3번의 1번 인형을 뽑아 바구니에 넣습니다.

바구니
1
3
4

그럼 보드는 다음과 같습니다.

1	2	3	4	5
0	0	0	0	0
0	0	0	0	0
0	2	5	0	1
0	2	4	4	2
3	5	1	3	1

board[1][2]의 값을 0으로 변경하고 basket에 [1] 추가

네 번째 크레인은 5번의 1번 인형을 뽑아 바구니에 넣습니다.

바구니
1
1
3
4

그럼 보드는 다음과 같습니다.

1	2	3	4	5
0	0	0	0	0
0	0	0	0	0
0	2	5	0	0
0	2	4	4	2
3	5	1	3	1

board[2][4]의 값을 0으로 변경하고 basket에 [1] 추가

이 때 아래의 값과 현재의 값이 1로 동일하기 때문에 현재 값과 아래의 값을 터트린다.
터트린 인형: 2개

바구니
3
4

다섯 번째 크레인은 1번의 3번 인형을 뽑아 바구니에 넣습니다.

바구니
3
3
4

그럼 보드는 다음과 같습니다.

1	2	3	4	5
0	0	0	0	0
0	0	0	0	0
0	2	5	0	1
0	2	4	4	2
0	5	1	3	1

board[4][0]의 값을 0으로 변경하고 basket에 [3] 추가

이 때 아래의 값과 현재의 값이 3로 동일하기 때문에 현재 값과 아래의 값을 삭제한다.
터트린 인형: 4개

바구니
4

여섯 번째 크레인은 2번의 2번 인형을 뽑아 바구니에 넣습니다.

바구니
2
4

그럼 보드는 다음과 같습니다.

1	2	3	4	5
0	0	0	0	0
0	0	0	0	0
0	0	5	0	1
0	2	4	4	2
0	5	1	3	1

board[2][1]의 값을 0으로 변경하고 basket에 [2] 추가

일곱 번째 크레인은 1번을 뽑느데 1번 라인은 비어있으므로 통과한다.

여덟 번째 크레인은 4번의 4번 인형을 뽑아 바구니에 넣습니다.

바구니
4
2
4

그럼 보드는 다음과 같습니다.

1	2	3	4	5
0	0	0	0	0
0	0	0	0	0
0	0	5	0	1
0	2	4	0	2
0	5	1	3	1

board[3][3]의 값을 0으로 변경하고 basket에 [4] 추가

전부 끝내고 터트린 인형의 수인 4를 반환한다.

이제 로직을 작성해보자.

우선 터트린 인형 개수를 담을 정수형 변수를 0으로 초기화, 바구니 배열을 빈 배열로 초기화를 진행한다.

명령의 개수만큼 움직어야 하므로 moves의 길이만큼 for문을 작성하고 어느 라인을 돌 것인지 체크한다.

그 후 board의 길이 만큼(정사각형이기 때문.) for문을 돌면서 0이 아닌 값을 찾는다.

그 값을 인형 변수에 저장하고 그 값은 0으로 변경한다.

만약 basket이 비어 있다면 append하고 다음 명령.

현재 basket 맨 위에 있는 값, 즉 맨 뒤 값이랑 비교해서 같으면 삭제 및 인형 개수 증가 + 2하기.

그렇지 않으면 계속 쌓는다.

최종적으로 터트린 인형 값을 반환한다.

그렇게 만든 풀이

def solution(board, moves):
    popped_dolls = 0
    basket = []
    
    for i in range(len(moves)):
        line = moves[i] - 1
        
        for j in range(len(board)):
            # 인형을 뽑고 그 자리는 인형이 없으므로 0으로 변경
            doll = board[j][line]
            board[j][line] = 0
            
            # 0은 인형이 없는 것이기 때문에 바로 다음 행으로 이동
            if doll == 0:
                continue
                
            # basket이 비어있다면 인형 추가 후 다음 명령
            if not basket:
                basket.append(doll)
                break
            
            # 바구니에 있는 인형과 지금 뽑은 인형이 같은 인형인 경우 터트리고 터트린 인형 개수 + 2
            if basket[-1] == doll:
                basket.pop()
                popped_dolls += 2
            # 그렇지 않으면 바구니에 추가하고 끝.
            else:
                basket.append(doll)
            
            # 완료되면 다음 행으로 넘어가는 것이 아니라 다음 명령으로 이동
            break
        
    
    return popped_dolls

좀 더 다듬고 리팩터링해본 결과

def grab_doll(board, col):
    for row in range(len(board)):
        if board[row][col] != 0:
            doll = board[row][col]
            board[row][col] = 0
            return doll
            
    return 0


def solution(board, moves):
    popped_dolls = 0
    basket = []
    
    for move in moves:
        col = move - 1
        
        doll = grab_doll(board, col)
        
        if doll == 0:
            continue
            
        if basket and basket[-1] == doll:
            basket.pop()
            popped_dolls += 2
        else:
            basket.append(doll)
            
    return popped_dolls

---

느낀점

로직 상으로는 해결할 수 있는 문제이지만 쓸 데 없는 코드도 있고 리팩터링할 요소가 많은 풀이였다.