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

# 해당 포스팅은 이제 막 알고리즘 공부를 시작한 초보 수준에서 작성했음을 이해해주시고, 비난보다는 따뜻한 조언을 부탁드립니다.

---

안녕하십니까, 간토끼입니다.

오늘은 프로그래머스(Programmers) 크레인 인형뽑기 게임 문제에 대해 다뤄보겠습니다.

2019년 카카오 개발자 겨울 인턴십 문제(Lv.1 수준)입니다.

 

1. 문제 링크

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

프로그래머스

문제가 길어서 어려울 거라고 예상했는데 난이도는 생각보다 어렵진 않았던 문제입니다.

크기가 N x N인 정사각형 격자에서 각 칸에 들어있는 인형을 뽑아서 바구니로 옮기는 문제입니다.

이때 옮기려는 인형이 바구니의 상단에 있는 인형과 같은 인형이라면 터뜨릴 수 있습니다. (테트리스같은 느낌이죠)

입력은 인형이 들어있는 2차원 배열 board와 어떤 칸을 뽑을지 동작을 결정하는 moves 배열이 주어지고, 옮기는 동작은 moves의 각 원소를 통해 결정됩니다.

터뜨린 인형의 개수를 구해서 출력하면 되는 문제입니다.

 

2. 접근 방법

다음과 같이 접근하였습니다.

먼저 입력으로 주어지는 2차원 배열은 row vector로 이루어진 배열입니다.

하지만 주어지는 move는 row가 아닌 column의 번호이므로, move에 의해 인형 뽑는 동작을 하기 위해서는 주어진 2차원 배열을 column vector들의 배열로 바꿔줘야 합니다.

일종의 행렬의 transpose라고 할 수 있겠네요.

이를 바꿔주고 나면 move에 의해 선택된 리스트에서 0이 아닌 원소를 집어서 basket으로 보내주고, 해당 위치는 0으로 업데이트 합니다.

집은 인형은 basket에 들어있는 최상단의 인형과 같은지 비교해줘야 하는데요.

만약 같다면 인형을 터뜨려야 하니깐요.

실제로 같다면, 최상단의 원소를 pop을 통해 꺼내주고, count에 2를 더해줍니다. (인형을 2개 터뜨렸다는 의미)

예를 들어 basket = [1,2,3,4]이고 집은 인형이 4라면 basket[-1] == 4이니까 터뜨릴 수 있겠죠?

그러면 basket.pop()을 통해 4를 꺼내주면 basket은 [1,2,3]이 됩니다. 스택 구조를 활용한 거죠.

이 흐름대로 구해주면 됩니다. 재밌는 문제네요!

 

3. 코드

def solution(board, moves):
    # (1) board를 n개의 column vector로 변환해야함.
    n = len(board) # board의 column 수
    column_board = [[0]*n for _ in range(n)]
    for i in range(n):
        board_i = board[i] # i번째 행
        for j in range(n):
            column_board[j][i] = board_i[j] # transpose
    
    # (2) moves의 move에 맞는 column vector에서 하나씩 추출
    basket = [] # 바구니
    cnt = 0 # 터뜨린 인형 count
    for move in moves:
        move = move-1 # column 지정 : 1번 move -> 0번 column
        target = column_board[move]
        i = 0
        while True:
            if i == n:
                # 해당 리스트 텅텅 빔 (0으로만 이루어진 list)
                break
            # 0이 아닌 원소가 나오면 break하고 basket으로 옮김
            if target[i] != 0:
                a = target[i] # 집은 인형
                column_board[move][i] = 0 # 해당 위치의 인형을 집었으므로 0으로 초기화
                if len(basket) == 0:
                    basket.append(a)
                    break
                else:
                    if basket[-1] == a: # 집은 인형이 basket의 마지막에 있던 거랑 같다면
                        basket.pop()
                        cnt += 2
                    else:
                        basket.append(a)
                    break
            else:
                i += 1
            
    answer = cnt
    return answer

 

감사합니다.

잘 읽으셨다면 게시글 하단에 ♡(좋아요) 눌러주시면 감사하겠습니다 :)

(구독이면 더욱 좋습니다 ^_^)

* 본 블로그는 학부생이 운영하는 블로그입니다.

따라서 포스팅에 학문적 오류가 있을 수 있으며, 이를 감안해서 봐주시면 감사하겠습니다.

 

---

- 간토끼(DataLabbit)

- B.A. in Economics, Data Science at University of Seoul