2019 카카오 개발자 겨울 인턴십 > 크레인 인형뽑기 게임 - Python, stack

 

 

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

프로그래머스

 

풀이 - 나의 생각

board의 최상단에 위치한 인형을 찾아

 

그 값이 stack의 이전 값과 같으면

 

stack에 있는 값도 pop하고 인형의 개수(+2) 추가

 

아니라면 stack에 저장해주고 넘어갑니다.

 

2019년도 카카오 인턴십에 나온 문제라는데

 

현재보다는 난이도가 낮은 듯 합니다.

 

좀 더 빠르게 풀 수 있는 방법이 뭘까 하다가

 

최상단에 있는 인형을 미리 조사해서 뽑아다 쓰는 방법을 해봤습니다.

 

속도는 거의 2배 차이 나네요.

 

코드

 

def solution(board, moves):
    answer = 0
    stack = []
    
    for move in moves:
        col = move - 1
        for i in range(len(board)):
            if board[i][col] > 0:
                doll = board[i][col]
                board[i][col] = 0
                
                if stack and stack[-1] == doll:
                    stack.pop()
                    answer += 2
                else:
                    stack.append(doll)
                break
    
    return answer

 

def solution(board, moves):
    answer = 0
    stack = []
    top = [-1] * len(board)
    
    for i, dolls in enumerate(board):
        for j, doll in enumerate(dolls):
            if doll > 0 and top[j] == -1:
                top[j] = i
                
    for i in moves:
        doll_index = top[i-1]
        if doll_index < len(board):
            doll = board[doll_index][i-1]
            top[i-1] = doll_index + 1
            if stack and stack[-1] == doll:
                stack.pop()
                answer += 2
            else:
                stack.append(doll)
    
    return answer

 

 

 

 

 

다음에 또 봐요