[프로그래머스 / Python] 크레인 인형뽑기 게임

문제

인형 뽑기 게임을 진행하면서 몇 개의 인형이 사라졌는지 출력하는 문제이다.

크레인이 작동한 위치에 따라 인형을 집어 올리고, 바구니(stack)로 이동하면서 인형이 연속되면 제거하여 사라진 인형 개수를 구한다.

풀이

• 2차원 배열과 스택을 활용해 문제를 풀 수 있다.

• 크레인을 작동시킨다.
  • move 위치에서 맨 위쪽부터 즉 row가 작은 순으로 탐색한다.
  • 인형이 있는 경우 인형 정보를 저장하고 board는 빈칸(0)으로 만든다.

• 동일한 인형일 경우 인형을 제거한다.
  • 새로 뽑은 인형의 정보와 basket에 담긴 마지막 인형이 동일하다면 마지막 인형을 제거하고 count에 2를 더한다.
  • 만약 동일한 인형이 아니라면 뽑은 인형을 basket에 담는다.
• count 된 숫자를 return 한다.

Python 코드

def solution(board, moves):
    basket = []  # 바구니
    count = 0    # 사라진 인형의 개수
    
    # 크레인을 작동시키는 moves 배열 순회
    for move in moves:
        column = move - 1 # move는 1부터 시작함으로
        
        # 해당 열에서 가장 위에 있는 인형 찾기
        for row in range(len(board)):
            if board[row][column] != 0: 
                doll = board[row][column] 
                board[row][column] = 0    
                
                # 바구니의 맨 위에 있는 인형과 동일한지 확인
                if basket and basket[-1] == doll:
                    basket.pop()  # 인형 제거
                    count += 2    # 뽑은 인형과 바구니에 있던 인형 2개 세어줌
                else:
                    basket.append(doll)  # 바구니에 인형 추가
                
                break
    return count

 

문제출처

https://school.programmers.co.kr/learn/courses/30/lessons/64061

프로그래머스