[프로그래머스] 2019 카카오 개발자 겨울 인턴십 - 크레인 인형뽑기 게임(Swift / Python 풀이)

programmers.co.kr/learn/courses/30/lessons/64061

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

스택 개념을 이용하여 푸는 문제다.

인형을 뽑을 때마다 담는 바구니가 스택이라고 생각하자.

 

스택에 인형을 담기 전에,

peek(마지막에 삽입된 값을 읽어옴) 값과 비교해서 같은 인형이면 pop(마지막에 삽입된 값을 꺼내옴/삭제) 한다.

다른 인형이면 뽑은 인형을 push(스택의 마지막에 값을 삽입함) 한다.

 

스택의 개념을 사용할 뿐, 배열로 작성해도 된다.

Swift의 경우 peek은 last, pop은 removeLast, push는 append를 이용한다.

Python3의 경우 peek은 list[-1], pop은 pop, push는 append를 이용한다.

 

크레인은 NxN 2차원 배열 보드의 칸(행)을 돌아다니며 인형을 뽑는다.

한번에 각 칸의 꼭대기에 있는 단 하나의 인형만 뽑을 수 있으므로

꼭대기 정보를 갖고 있는 배열 `top`을 가지고 있으면 편리할 것이다.

꼭대기는 각 행에서 0이 아닌 값을 갖고 있는 가장 작은 열이다.

 

특정 칸의 꼭대기 값이 N(보드의 크기)과 같다면, 해당 칸에는 인형이 아무것도 없다는 뜻이다.

인형을 뽑을 때 마다 꼭대기 정보를 갱신 (+1) 해주면 된다.

 

Swift 풀이

import Foundation

func solution(_ board:[[Int]], _ moves:[Int]) -> Int {
    var top = Array(repeating: -1, count: board.count)
    var basket:[Int] = []
    var count = 0
    for move in moves {

        // 꼭대기 정보가 없으면 찾는다
        if top[move-1] == -1 {
            for row in 0..<board.count {
                if board[row][move-1] != 0 {
                    top[move-1] = row
                    break
                }
            }
        }

        // 해당 칸에 인형이 하나도 없으면 다음 칸
        if top[move-1] >= board.count {continue}

        let doll = board[top[move-1]][move-1]
        if basket.last == doll { 
            // 같은 인형이 연속이면 터뜨리고 count 증가
            basket.removeLast()
            count += 2
        } else { 
            // 다른 인형이면 바구니에 인형을 쌓는다
            basket.append(doll)
        }

        // 꼭대기 정보를 갱신한다
        top[move-1] += 1
    }
    return count
}

 

Python 풀이

def solution(board, moves):
    answer = 0
    basket = []
    top = {}

    for move in moves: # move칸의 인형

        if move not in top: # move칸의 꼭대기 정보가 없는 경우
            top[move] = len(board)

            for i in range(len(board)): # move 칸에서 0이 아닌 칸이 나올 때 까지 탐색
                if board[i][move-1] != 0:
                    top[move] = i
                    break

        # move칸의 꼭대기가 board의 높이와 같다면, move칸은 빈칸이다.
        if top[move] >= len(board):
            continue    # 다음칸으로 이동


        doll = board[top[move]][move-1] # move칸에서 뽑은 인형
        if len(basket) > 0 and basket[-1]==doll: # 연속으로 같은 인형일 경우 -> 터짐
            answer += 2
            basket.pop()
        else: # 연속으로 같은 인형이 아닐 경우 -> basket에 인형 추가
            basket.append(doll)

        board[top[move]][move-1] = 0 # 뽑은 인형은 0으로 변경
        top[move] += 1 # 꼭대기 정보 업데이트

    return answer