[Programmers] Level 1 - 크레인 인형 뽑기

김지원·2022년 2월 3일

Level 1 python 카카오 프로그래머스

Python으로 공부하는 코딩테스트

목록 보기

1/82

문제 링크
https://programmers.co.kr/learn/courses/30/lessons/64061

어떻게 풀었나?

1-1. board 배열의 행과 열을 바꾼다.

[0, 0, 0, 0, 0]              [0, 0, 0, 4, 3]
[0, 0, 1, 0, 3]              [0, 0, 2, 2, 5]
[0, 2, 5, 0, 1]     --->     [0, 1, 5, 4, 3]
[4, 2, 4, 4, 2]              [0, 0, 0, 4, 3]
[3, 5, 1, 3, 1]              [0, 3, 1, 2, 1]
      arr                     list(zip(*arr)

💡 2차원 배열 행과 열 바꾸는 방법
new_arr = list(zip(*arr))

💭 왜? WHY?

board 은 인형뽑기 기계의 형태 그대로 표현된 2차원 배열이다.
즉, 인형뽑기 기계의 맨 위의 첫 번째 줄이 board의 첫 번째 행이 되고, 두 번째 줄은 board의 두 번째 행이 된다.

하지만 크레인이 인형을 뽑을 때는 단위가 board의 행이 아니라 열이다.

예를 들어, 크레인을 작동시킨 위치가 1 일 경우,
크레인은 board의 첫 번째 열의 맨 위에 있는 인형을 뽑게 된다.

1-2. board 배열을 덱으로 바꾼다.

board = deque(map(deque, zip(*board)))

💭 왜? WHY?

행과 열을 바꾼 board 배열은 아래와 같다.

[0, 0, 0, 4, 3]
[0, 0, 2, 2, 5]
[0, 1, 5, 4, 3]
[0, 0, 0, 4, 3]
[0, 3, 1, 2, 1]

board의 행과 열을 바꾸면, 인형뽑기 기계의 형태가 아래와 같이 바뀌었다고 볼 수 있다. 뭔가 익숙한 구조가 보이지 않나?!

스택을 왼쪽으로 90도 기울인 형태와 동일하다. LIFO(Last In, First Out) 형태다. 즉, 제일 마지막에 들어간 요소가 제일 먼저 나올 수 있다.

따라서 덱을 사용하였다.

2. 예외조건 처리하기

문제 설명에 보면 예외조건이 있다.

크레인 작동 시 인형이 집어지지 않는 경우는 없으나 만약 인형이 없는 곳에서 크레인이 작동시키는 경우에는 아무런 일도 일어나지 않습니다.

따라서 아래와 같이 예외조건 처리를 해주었다.

if not board[move-1]:    # 비어 있으면 skip, 아무 일도 일어나지 않음
	continue

3. 크레인으로 인형 뽑기

while True:
	popped_doll = board[move-1].popleft()
    if popped_doll != 0:
    	break

예를 들어 board[1]는 아래와 같다.

[0, 0, 0, 4, 3]

문제 설명에 보면 board에 담겨 있는 정수에 대해 알려주고 있다.

0은 빈 칸을 나타냅니다.

1~100의 각 숫자는 각기 다른 인형의 모양을 의미하며 같은 숫자는 같은 모양의 인형을 나타냅니다.

따라서 board[move-1].popleft() 작업은 pop한 정수가 0이 아닐 때까지 수행되어야 한다.
popped_doll이 0이 아닌 정수일 경우, 해당 while 문을 탈출하게 된다.

4. 뽑은 인형을 바구니에 넣기

뽑은 인형을 바구니에 넣는 경우는 일어날 수 있는 일은 아래와 같다.

뽑은 인형을 바구니에 넣는다.(넣기만 한다.)

바구니가 비어 있는 경우 또는
바구니가 비어 있지 않을 경우, 바구니 안 맨 위의 인형이 넣을 인형과 다른 인형일 경우

뽑은 인형을 바구니에 담는 과정에서 터트려져서 2개의 인형이 사라질 수 있다.

바구니 안 맨 위의 인형이 넣을 인형과 같은 인형일 경우

위를 아래와 같은 조건문으로 표현할 수 있다.

# 1. 뽑은 인형을 바구니에 넣기만 한다.
if not basket or basket[-1]!=popped_doll:     
	basket.append(popped_doll)
# 2. 뽑은 인형을 바구니에 담는 과정에서 2개의 인형이 터트려져서 사라진다.
elif basket[-1] == popped_doll:
	basket.pop()
    answer += 2

최종 코드는 아래와 같다.

💻최종 코드

from collections import deque

def solution(board, moves):
    answer = 0
    # board의 각 열을 덱으로 바꾸기
    board = deque(map(deque, zip(*board)))
    basket = []
    #print(board)
        
    for move in moves:
        #print("move: ", move)
        if board[move-1]:
            while 1:
                popped_doll = board[move-1].popleft()
                if popped_doll!=0:
                    break
                #print("popped_doll: ", popped_doll)
            if not basket or basket[-1]!=popped_doll:
                basket.append(popped_doll)
            elif basket[-1] == popped_doll:
                basket.pop()
                answer += 2
    return answer