[Programmers] 2019 카카오 개발자 겨울 인턴십 - 크레인 인형뽑기 게임 (Python)

코딩 1일 1문제! 오늘의 문제는 2019 카카오 개발자 겨울 인턴십 문제였던! 크레인 인형뽑기 게임 입니다.

코딩테스트 연습 - 크레인 인형뽑기 게임

👨🏻‍💻 문제 풀이

인형이 들어있는 인형뽑기 게임이 있고 인형을 들어올리는 크레인이 움직이는 경로가 주어지고

각 경로에서 뽑은 인형을 하나의 바구니에 담을때 같은 인형끼리 붙을 경우 인형이 터지면서 사라진다고 할때

터져서 없어진 인형의 개수를 구하는 문제입니다.

딱 터져서 없어진다! 라는 것을 보았을 때 스택의 개념을 활용해서 풀면 되겠다! 라는 생각이 들었습니다.

 

그래서 바구니 ( basket ) 를 스택으로 하나 만들어주었습니다.

basket = [0]

0을 넣어준 이유는 -1로 접근하였을때 오류가 나지 않도록 하기 위해서 0을 하나 넣어주었습니다.

 

크레인으로 인형을 뽑는다고 한다면 각 위치의 가장 위쪽 인형을 뽑게 됩니다.

1 -> 5 -> 5 -> 3 순서로 뽑았을 경우 위와 같이 바구니에 쌓이고 같은 인형이 만났을때 터져 없어지는 것을 볼 수 있습니다.

그럼 크레인이 각 위치를 돌면서 뽑을 수 있는 인형은 어떻게 구하느냐!

위와 같이 인형이 있는 현재 상황 ( board )을 2차원 리스트로 제공합니다.

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

이를 인형 그림 처럼 배열해보면 위와 같습니다.

그럼 각 열의 값이 각 위치의 인형의 값인데 0이면 비어있고 0이 아니면 인형이 있는 것 입니다.

각 위치에 인형이 비어있다면 크레인이 해당 위치에 갔을때 아무것도 하지 않는 조건이 있습니다.

N = len(board)
idx_list = [0 for _ in range(N)]

for i in range(N):
    for j in range(N):
        if board[j][i] != 0:
            continue
        idx_list[i] += 1

먼저 각 위치에서 크레인이 인형을 집으려고 할때 가져갈 수 있는 인형의 위치를 구합니다.

각 열에서 0이 아닌 위치의 행 값을 저장했습니다.

for move in moves:
    if idx_list[move-1] != N:
        if board[idx_list[move-1]][move-1] != basket[-1]:
            basket.append(board[idx_list[move-1]][move-1])
            idx_list[move-1] += 1
        else:
            basket.pop()
            idx_list[move-1] += 1
            answer += 2

그 다음 크레인이 이동하는 경로를 하나씩 가져와서 해당 위치에 인형이 있을 경우에만

인형을 꺼내 바구니에 넣고

바구니의 맨 위에 해당 인형이 있으면 정답 +2 + 바구니에서 맨 위 인형꺼내기

바구니의 맨 위에 있는 인형이 크레인으로 집은 인형과 다를때는 그냥 꺼낸 인형을 바구니에 넣기만하기의 

방식으로 진행합니다.

 

전체 코드는 아래를 참고해주세요.

👨🏻‍💻 코드 ( Solution )

def solution(board, moves):
    answer = 0
    basket = [0]
    
    N = len(board)
    idx_list = [0 for _ in range(N)]
    
    for i in range(N):
        for j in range(N):
            if board[j][i] != 0:
                continue
            idx_list[i] += 1
        
    for move in moves:
        if idx_list[move-1] != N:
            if board[idx_list[move-1]][move-1] != basket[-1]:
                basket.append(board[idx_list[move-1]][move-1])
                idx_list[move-1] += 1
            else:
                basket.pop()
                idx_list[move-1] += 1
                answer += 2
        
    return answer

GitHub - SOMJANG/CODINGTEST_PRACTICE: 1일 1문제 since 2020.02.07