[Level 1] [python] 크레인 인형뽑기 게임

문제

파이썬 풀이

from collections import deque
def solution(board, moves):
    length = len(board)
    dict = {}
    stack = deque()
    answer = 0
    for i in range(length) :
        dict[i+1] = deque()
        for j in range(length) :
            if board[j][i] == 0 :
                continue
            dict[i+1].append(board[j][i])
    # 크레인 게임 시작
    for number in moves :
        if dict[number] :
            # 해당 number줄에 인형이 있다면
            new = dict[number].popleft()
            if stack and stack[-1] == new :
                answer += 2
                stack.pop()
            else :
                stack.append(new)
            
    return answer

세로 스택으로 변경

for i in range(length) :
        dict[i+1] = deque()
        for j in range(length) :
            if board[j][i] == 0 :
                continue
            dict[i+1].append(board[j][i])

처음에는 자료들이 가로로 연결되어있다.

크레인이 들어가는 방향은 세로이기에 세로로 연결되도록 자료를 조금 변경했다.

그림으로 나타내면 아래와 같다.

처음 for문이 세로 형태로 스택을 쌓는 과정이다. 같은 번호에 있는 세로줄 스택을 딕셔너리에 번호를 키로 저장하였다. 그리고 0의 경우는 인형이 없음을 의미하므로 집어넣지 않았다.

크레인 뽑기 시작

for number in moves :
        if dict[number] :
            # 해당 number줄에 인형이 있다면
            new = dict[number].popleft()
            if stack and stack[-1] == new :
                answer += 2
                stack.pop()
            else :
                stack.append(new)

반복문을 통해 moves의 원소에 하나하나 접근한다.

접근한 값이 뽑을 스택 칸을 의미하므로, 딕셔너리 키를 이용해 해당 스택에 접근한다.

만약에 딕셔너리가 비어있지 않다면 인형이 들어있다는 뜻이고, 비어있다면 인형이 들어있지 않다는 뜻이다.

이번에 뽑게될 인형을 new변수에 저장해둔다.

popleft를 통해 앞에서 뽑은 이유는 앞 단계에서 데이터를 저장할 때 위에 부터 먼저 저장되어 그림과는 거꾸로 된 형태로 저장되었기 때문이다.

stack은 뽑은 인형을 쌓아두는 스택이다.

만약에 스택이 비어있지 않고, 그래서 현재 가장 위에있는[-1] 인형과 현재 뽑은 인형 new가 같다면,

그 인형들은 터뜨리므로 가장 위에있는 변수를 pop을 통해 꺼내고, 2개의 인형을 터뜨리므로 결과 값에 +2를 해준다.

하지만 스택이 비어있거나, 일치하지 않는 경우 그대로 그냥 새로운 인형 new를 stack에 추가해준다.