[PG64061] 크레인 인형뽑기 게임

프로그래머스

🚩 문제 설명

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

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

인형을 뽑기 전

◾ N x N의 격자가 주어진다.

◾ 각 인형은 아래에서부터 차곡차곡 쌓여있다.

◾ 게임 사용자는 크레인을 좌우로 움직여서 인형을 뽑을 수 있다.

◾ 그리고 오른쪽의 빈 바구니에 인형을 담을 수 있다.

인형을 뽑고난 후

◾ 인형을 뽑고 오른쪽 바구니에 연속된 인형이 담겨졌을 시 두 인형이 터트려져 사라지게 된다.

◾ 인형이 없는 곳에서 크레인을 작동시키면 아무런 일도 일어나지 않는다.

◾ 터트려진 인형의 수를 구하는 문제

 

 

---

 

 

✅ 입출력

board : 인형이 들어있는 정사각형의 격자 배열
moves : 인형을 집기 위해 크레인을 작동시킨 위치가 담긴 배열
return ➡️ 터트려진 인형의 갯수를 반환

board	moves	return
[[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,5,3,5,1,2,1,4]	4

 

 

---

 

 

📑 문제 풀이

with 파이썬 (Python)

def solution(board, moves):
    ans = 0
    stack = []

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

                if len(stack) > 1:
                    if stack[-1] == stack[-2]:
                        stack.pop()
                        stack.pop()
                        ans += 2
                break
    return ans

◾ 스택을 사용해서 쉽게 풀 수 있었다.

◾ 세로로 움직여야 하기 때문에 유의할 필요가 있다.

만약 moves = [1, 5, 3, 5, 1, 2, 1, 4] 라면

i	j	i - 1	board[j][i-1]
1	0 1 2 3 4	0	0 0 0 4 3 : board에서 1열만 훑는다
5	0 1 2 3 4	4	0 3 1 2 1 : board에서 5열만 훑는다
3	0 1 2 3 4	2	0 1 5 4 1 : board에서 3열만 훑는다

◾ 이런식으로 열만 훑으면서 반복문을 돈다.

◾ stack 배열에 해당 값을 가져와서 넣고 값은 0으로 만들어준다.

◾ 만약 stack 배열에서 제일 끝과 제일 끝 앞에 인덱스의 값이 같다면 둘다 빼내준다.

• 같은 인형이면 터트려주는 과정을 이른다.
• 두 개의 인형이 동시에 터지므로 ans 에 2씩 더해준다.

 

 

 

 

 

 

 

 

 

---