Lv1. 크레인 인형 뽑기 ( Python )

Lv1. 크레인 인형 뽑기
본 문제는 2019 카카오 개발자 겨울 인턴십 출제문제이다. 카카오에서 대표적으로 출제되는 문제 유형인 게임 관련 유형의 문제이다. 본 문제는 직관적인 문제 설명과 간단한 로직으로 해결할 수 있는 문제이며 직관적인 문제 접근을 통해 풀이가 가능하다.

# 문제 설명

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

# 제한 사항

  • board 배열은 2차원 배열로 크기는 5 x 5 이상 30 x 30 이하입니다.
  • board의 각 칸에는 0 이상 100 이하인 정수가 담겨있습니다.
    • 0은 빈 칸을 나타냅니다.
    • 1 ~ 100의 각 숫자는 각기 다른 인형의 모양을 의미하며 같은 숫자는 같은 모양의 인형을 나타냅니다.
  • moves 배열의 크기는 1 이상 1,000 이하입니다.
  • moves 배열 각 원소들의 값은 1 이상이며 board 배열의 가로 크기 이하인 자연수입니다.

# 입출력 예

Board moves return
[[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

문제 해결 시 고려사항

  • 주어지는 배열 내 열에 대한 Stack화 작업

    인형 뽑기가 진행되는 보드는 N * N 크기의 격자로 주어지며, 주어지는 moves 배열 내의 원소에 해당하는 열의 맨 위에 위치한 인형을 뽑아 바구니에 넣는 작업을 반복한다. 입력으로 주어지는 moves에 따라 보드의 열에 대한 반복접근이 이루어지기 때문에 접근 편의성을 위하여 인형 뽑기 보드에 각 열에 대한 Stack화 작업을 취한다. 이 작업을 선행함으로써 전치화 작업 또한 자연적으로 이루어지며 이로 인해 열에 대한 반복 접근 및 가장 위 인형에 대한 접근 용이성을 보장받을 수 있다.

 #board 각 열에 대한 stack화 및 전치화 작업
    for j in range(board_len):
        temp = []
        for i in range(board_len):
            temp.append(board[i][j])
        stacks.append(temp)


  • 인형을 바구니로 이동시킬 때의 검증 및 확인 작업

크레인이 인형을 집어 바구니에 놓을 때 고려해야하는 것은 두 가지다.

  1. 크레인 작업이 이루어지는 열 내에 뽑을 인형이 있는가?

    ( 없다면 해당 과정은 무시 )

  2. 집은 인형을 바구니에 놓을 때 동일 인형이 인접해있는지 검사 및 처리

    ( 동일한 인형이 인접해 있다면 제거 및 개수 카운트 )

1번 조건의 경우, stack화 한 해당 move칸 라인 내를 순차 탐색하면서 0은 무시함으로써 해결하였다

라인 내의 인형이 존재하며 인형을 집었다면, 인형이 있던 위치에 0을 삽입하고 현재 바구니 스택을 검증한다. 바구니가 비어있다면 인형을 삽입하고 종료시킨다. 만약 바구니에 인형이 있다면(1개 이상), 바구니 맨 위에 위치한 인형이 현재 집은 인형과 같은지 확인하는 검증과정을 거친다. 인형이 같으면 두 인형을 삭제해야하므로 마지막 요소를 pop() 하고 카운트를 증가시키고 아니라면 인형을 바구니에 집어넣고 종료시킨다.

  #moves 내의 move 순차처리
    for move in moves:
        for j in range(board_len):
            if stacks[move-1][j] == 0:
                pass
            else:
                #해당 열의 제일 위 인형을 pop하여 bakset으로 이동
                basket.append(stacks[move-1].pop(j))
                stacks[move-1].insert(j,0)
                #basket 내에 연속되는 인형이 있으면 해당 인형들을 지우고 answer 업데이트
                if(len(basket)>1):
                    if(basket[len(basket)-1] == basket[len(basket)-2]):
                        basket.pop()
                        basket.pop()
                        answer+=2
                break



전체 코드

def solution(board, moves):
    answer = 0
    stacks = []
    basket = []
    board_len = len(board[0])
    #board 각 열에 대한 stack화 및 전치화 작업
    for j in range(board_len):
        temp = []
        for i in range(board_len):
            temp.append(board[i][j])
        stacks.append(temp)
    #moves 내의 move 순차처리
    for move in moves:
        for j in range(board_len):
            if stacks[move-1][j] == 0:
                pass
            else:
                #해당 열의 제일 위 인형을 pop하여 bakset으로 이동
                basket.append(stacks[move-1].pop(j))
                stacks[move-1].insert(j,0)
                #basket 내에 연속되는 인형이 있으면 해당 인형들을 지우고 answer 업데이트
                if(len(basket)>1):
                    if(basket[len(basket)-1] == basket[len(basket)-2]):
                        basket.pop()
                        basket.pop()
                        answer+=2
                break
    return answer