[Programmers] 크레인 인형뽑기 게임

프로그래머스 - 크레인 인형뽑기 게임: https://programmers.co.kr/learn/courses/30/lessons/64061 

데이터 구조 

각 고유의 카카오 이모지는 숫자를 의미합니다. 

좌측 테이블: NxN 

우측 테이블: Mx1 (M: NxN) 

규칙1: 같은 모양 인형 2개가 쌓이면 제거됨 

규칙2: 인형이 없으면 크레인 아무 동작 안 함 

규칙3: Mx1 우측 테이블은 모든 인형이 들어갈 수 있음. 

FILO 구조 

주어지는 입력

게임에서 격자의 상태가 담긴 2차원 배열 board

인형을 집기 위해 작동시킨 위치가 담긴 배열 moves

출력

크레인이 모두 작동시킨 후 터트려져 사라진 인형의 개수 answer 

입출력 예시

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	-	0
5	1	0
3	1	2
5	3	2
1	-	2
2	3	4
1	-	4
4	2	4

의사코드 

1. 열단위 처리가 용이하도록, numpy를 활용한다.
2. moves에 있는 위치의 열을 가져온다. 
3. 앞의 숫자와 동일하면 두 개의 원소를 제거한다. 
   1. 제거 방식1: 슬라이싱
   2. 제거 방식2: pop
4. 제거 횟수를 세서 x2(2개씩 제거하니까) 반환한다. 

실패 코드 

def solution(board, moves):
    """
    board: 게임에서의 격자 상태에 인형이 담긴 NxN 2차원 배열
    moves: 인형을 담는 Mx1 배열(M: NxN) 
    cnt: 동일한 인형이 2개일 때 제거한 인형의 개수 총합
    """

    cnt = 0
    basket = []
    
    for m in moves:        
        out = board[m-1][-1]
        # print(f'고른 인형: {m, out}') # index = m-1
    
        board[m-1] = board[m-1][:-1]
        # print(f'길이: {len(board[m-1][:])}')
        
        if out != 0:
            # print(out, basket)
            if len(basket) > 0 and (out == basket[-1]):
                basket.pop(-1) 
                cnt += 1
            else:
                basket.append(out)        
    return cnt*2

if __name__ == '__main__':
    b = [[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]]	
    m = [1,5,3,5,1,2,1,4]

    print(solution(b, m))

실행 코드

def solution(board, moves):
    """
    board: 게임에서의 격자 상태에 인형이 담긴 NxN 2차원 배열
    moves: 인형을 담는 Mx1 배열(M: NxN)
    cnt: 동일한 인형이 2개일 때 제거한 인형의 개수 총합
    """

    cnt = 0
    basket = []
    for m in moves:
        for b in range(len(board)):
            doll = board[b][m-1]
            if doll != 0:
                basket.append(doll)
                board[b][m-1] = 0
                if len(basket) >= 2:
                    if basket[-1] == basket[-2]:
                        basket.pop(-1)
                        basket.pop(-1)
                        cnt += 2
                break
    return cnt


if __name__ == '__main__':
    b = [[0, 0, 0, 0, 1],
         [0, 0, 1, 0, 3],
         [0, 2, 5, 0, 1],
         [4, 2, 4, 4, 2],
         [3, 5, 1, 3, 1]]
    m = [1, 5, 3, 5, 1, 2, 1, 4]

    print(solution(b, m))

실행 시간

테스트 1 〉	통과 (0.02ms, 10.3MB)
테스트 2 〉	통과 (0.03ms, 10.3MB)
테스트 3 〉	통과 (0.03ms, 10.2MB)
테스트 4 〉	통과 (1.78ms, 10.2MB)
테스트 5 〉	통과 (0.02ms, 10.3MB)
테스트 6 〉	통과 (0.03ms, 10.2MB)
테스트 7 〉	통과 (0.13ms, 10.1MB)
테스트 8 〉	통과 (0.56ms, 10.2MB)
테스트 9 〉	통과 (0.51ms, 10.2MB)
테스트 10 〉	통과 (0.58ms, 10.3MB)
테스트 11 〉	통과 (1.19ms, 10.3MB)