2019 카카오 개발자 겨울 인턴십 풀이

Level 1 - 크레인 인형뽑기 게임 풀이
Level 2 - 튜플 풀이
Level 3 - 불량 사용자 풀이
Level 4 - 호텔 방 배정 풀이
Level 3 - 징검다리 건너기 풀이

프로그래머스 - 크레인 인형뽑기 게임 링크
(2022.11.01 기준 Level 1)

문제

각 행과 열의 크기가 N인 정사각 격자의, 인형이 밑에서부터 쌓여 있는 인형 뽑기 게임 화면이 있고, 크레인을 이용하여 각 위치에서 순서대로 인형을 집어 올려 바구니에 담는다.
만약 바구니에 같은 모양의 인형 두 개가 연속해서 쌓이면 그 두 인형은 터진다고 했을 때
터뜨려져 사라진 인형의 개수 반환

알고리즘

크레인의 위치 순서대로 뽑는다고 했을 때 뽑힐 인형을 바로 구할 수 있도록, 그리고 터질 인형을 구할 수 있게, 게임 화면과 바구니를 직접 구현해야 한다.

풀이

각 열마다 인형이 쌓여 있다. 그리고 인형은 맨 위부터 뽑힌다. 이는 각 열은 스택에 해당한다. 그러므로 각 열마다 맨 아래부터 인형이 있는지 검사하며 있다면 그 인형을 각 스택에 쌓고 스택을 전부 모아 차례대로 저장해둔다. 그렇다면 크레인이 작동할 때, 작동할 특정 위치의 스택에서 pop하면 인형이 뽑히게 되는 것이다.

그럼 이제 moves 순서대로 크레인을 작동시키면 된다.
그리고 뽑은 인형과 바구니의 마지막 인형을 비교하여 같다면 두 인형 다 터뜨리면 된다.
물론 결과엔 +2를 해주면 된다.

여기서 주의해야 할 점은 인형을 뽑을 때나 바구니의 마지막 인형과 비교할 때나 무조건 그 리스트가 비어있지 않은지 확인해야 한다.
무턱대고 pop 하거나 마지막 인덱스에 접근한다면, 그 리스트가 비어있으면 오류가 난다.

코드

def solution(board, moves):
    N = len(board) # 행과 열의 크기

    # 크기만큼 리스트를 담은 stacks를 만든다.
    # 각 리스트는 격자의 각 열을 나타낸다.
    stacks = [[] for _ in range(N)]
    for j in range(N):
        for i in range(N - 1, -1, -1):
            if board[i][j]: # 인형이 있다면
                stacks[j].append(board[i][j]) # 각 열에 해당하는 리스트에 쌓는다.
            else: # 인형이 없다면 앞으로도 없으므로 break
                break

    basket = [] # 바구니
    answer = 0 # 터진 인형
    for move in moves: # moves 차례대로
        if stacks[move - 1]: # 만약 인형이 남아있다면
            doll = stacks[move - 1].pop() # 뽑는다.
            # 만약 바구니에 인형이 있고 마지막 인형이 뽑은 인형과 같다면 두 인형을 터뜨리자.
            if basket and basket[-1] == doll:
                basket.pop()
                answer += 2
            else: # 아니면 바구니에 뽑은 인형을 쌓는다.
                basket.append(doll)

    return answer

여담

Lv 1 답게 아주 간단한 문제였다.
그리고 저번에 풀었던 행렬과 연산 문제를 푼 것이 아주 도움이 된 것 같다.
자료구조에 좀 더 능숙해진 느낌?