2019 카카오 개발자 겨울 인턴십 > 크레인 인형 뽑기 게임 코드 풀이

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

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

 

문제

크레인이 내려오면 인형을 뽑아 맨 오른쪽 칸에 넣게 되는데

위아래로 같은 인형이 쌓이면 터져 없어지게 된다.

이때 없어지는 인형의 갯수를 세는 것이다.

 

- 매개변수

게임 화면의 격자의 상태가 담긴 2차원 배열 board

인형을 집기 위해 크레인을 작동시킨 위치가 담긴 배열 moves

 

=> 크레인을 모두 작동시킨 후 터트려져 사라진 인형의 개수를 return 하도록 solution 함수를 완성해주세요.

- 문제 풀이

(1) 풀이(복잡)

* 맨 오른쪽 스택: final stack

1. 2차원 배열의 board에서 열끼리의 스택 생성 (ex) 위처럼 5x5 인 경우 5개의 세로 스택을 만드는 것(stack[0~4])

2. moves(i)의 수를 받아 stack [i-1]에서 pop 하여 final stack 에 집어 넣음.

3. final stack에 넣기 전 스택의 top 과 지금 넣을 값을 비교하여 넣는다.

temp = []
count = 0
final_stack = []
top = []

for i in range(5):
    for j in range(4,-1,-1):#4,-1,-1 넣을때 부터 거꾸로 넣어야 나옴.
        if board[j][i] != 0:
            temp.append(board[j][i]) #each stack 1 line

    if i == 0:
        stack = [temp] # [[0]]

    else:
        stack.append(temp) # [stack[0],stack[1],stack[2]...]

    temp = []
            
            
for i in moves:

    if not stack[i-1]:# stack is empty
        continue
    
    else:
        if not final_stack:#empty
                #push
            final_stack.append(stack[i-1].pop())
            top = final_stack[-1] 
            
        else:
            tmp = stack[i-1].pop()
            
            if top == tmp:
                final_stack.pop() #final이 빌 경우가 발생
                count += 2
            
            else:
                final_stack.append(tmp)
                
            if final:
                top = final_stack[-1]
                

print("answer:",count)

 

=> 이 경우 단점

1. board자체가 이미 2차원 배열인데 굳이 스택으로 또 2차원 배열을 만들어 버림.. // 배열도 제대로 모르는 듯^^..

2. final_stack에서 똑같으면 제거한 후에 top = final_stack[-1]을 해버리는 바람에 final stack이 비는 걸 간과하지 못해서 런타임 에러가 났었다^^.. 덕분에 마지막에 if final: top = final_stack[-1] 라는 굉장히 덧붙이는 코드를 적어 쓸데없이 길어진 느낌이 팍팍 든다^!^

=> 결론: 머리로만 스택을 이해했지 파이썬과 배열에서 어떻게 스택을 풀이해야 하는 지는 익숙해지지않은 모양..

 

(2) 개선된 코드

(봉원사스님 , 최승호 , mjjin0103 , milliwonaire , 명훈 외 34 명)

def solution(board, moves):
    stacklist = []
    answer = 0

    for i in moves:
        for j in range(len(board)):
            if board[j][i-1] != 0:
                stacklist.append(board[j][i-1])
                board[j][i-1] = 0

                if len(stacklist) > 1:
                    if stacklist[-1] == stacklist[-2]:
                        stacklist.pop()
                        stacklist.pop()
                        answer += 2     
                break

    return answer
    

 

 * 크레인에서 뽑아 담는 박스 = stacklist

1. board의 배열에서 moves에 따른 열의 박스로 가 인형을 뽑아 stacklist에 담는다.

    이때, 0이면 비어 있는 것이므로 != 0 인 것을 담는다.

2. stacklist에 담았으면 비어있어야 하므로 뽑은 자리엔 0을 대입한다.

3. stack list에 인형을 2개이상 갖고 있으면 [-1],[-2]를 비교하고 같으면 두개를 pop시켜 없앤다. 

4. 다 했으면 이는 moves 1번의 일 이므로 break 하여 다음 moves 수를 진행한다.

 

 

- 배울 점

• moves에 따라서 크레인이 번호 박스에서 인형을 뽑을 것이기 때문에 board 배열의 인덱스를 moves와 연결 시켰다.
• board 2차원 배열에서도 가장 위의 인형을 뽑으려면 행 인덱스의 수가 낮을 수록 높은 인형을 뽑는 것이다.(인덱스 잘 생각)
• 인형을 없애는 방법을 굳이 스택을 만들어 pop 시켜야한다고만 생각 했는데, 
  • 문제에서 말한 것 처럼 0일때가 빈 상태이므로 배열에 0을 대입해도 된다.

=> 크레인을 보자마자 스택 문제라고 생각하여 없애려면 무조건 pop시켜야 한다고 생각함, 배열 자체도 잘 활용하면 스택으로 사용 가능하다. 자료구조랑 알고리즘을 잘 섞어쓰는 것이 중요.