[알고리즘] 2019 카카오 개발자 겨울 인턴십 - 크레인 인형뽑기 게임

def solution(board, moves):
    
    answer = 0
    stack = []
    
    for i in moves:
        for j in board:
            if j[i-1] == 0: 
                continue
            else:
                if len(stack) == 0:
                    stack.append(j[i-1])
                    j[i-1] = 0
                    break
                else:
                    stack.append(j[i-1])
                    j[i-1] = 0
                    if stack[-1] == stack[-2]:
                        stack.pop()
                        stack.pop()
                        answer += 2
                    break
    return answer

문제와 입출력 예

board = [[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]]
moves = [1,5,3,5,1,2,1,4]

<output>
4

풀이과정

1. 이중 for문을 사용한다.
   • moves 배열을 반복하며 순서대로 위치에서 인형을 빼낸다.
   • board 배열의 첫 번째 인덱스가 가장 위에 있는 인형이다. 즉, board 배열을 반복하면서, 칸이 비어 있는 경우에는 다음 칸으로 내려온다.
2. 문제에서 주어진대로 0 값을 만나면, 다음 칸으로 이동한다.
3. 뽑아낸 인형이 쌓일 배열 stack을 만든다.
   • stack이 비어있으면, board에서 뽑아낸 원소를 넣어주고 해당 원소를 0으로 바꾼다.
   • stack이 비어있지 않으면, 뽑아낸 원소를 넣어주고 stack의 맨 위 원소와 아래 원소를 비교하여 같으면 뽑아낸다.