-
64061. 크레인 인형뽑기 게임(Python, Programmers Level 1)Programmers 2022. 9. 4. 22:13
문제 설명
크레인 게임을 통해 각 칸에서 캐릭터 인형을 뽑으며,
뽑은 인형을 쌓았을 때 동일한 인형이 겹친다면 터뜨려지면서 바구니에서 사라지게 됩니다.
게임을 진행하면서 폭발하는 총 개수는 몇 개인가요?
코드
n * n 크기의 board가 입력으로 주어지므로, n은 len(board)와 같습니다.
n = len(board)
입력받은 board는 행을 기준으로 리스트를 순회하기 좋은 형태이나,
인형을 뽑을 때는 열을 기준으로 뽑아가는 것이 편하기에 그렇게 변경합니다.
board를 순차적으로 순회한다면, 위쪽 행부터 순회되어 먼저 뽑힐 인형부터 저장되게 되는데, 이를 빼내려고 한다면 앞에서부터 빼내는 형태가 될 것입니다.
pop_arr = [deque() for _ in range(n)] for b in board: for i, doll in enumerate(b): if doll != 0: pop_arr[i].append(doll)
위와 같이 deque를 사용하여 앞에서부터 빼내기 좋은 형태를 만들 수 있습니다.
deque 없이 진행하기 위해서는 board를 뒤집어 아랫줄부터 입력되게 하면 됩니다.
pop_arr = [[] for _ in range(n)] for b in reversed(board): for i, doll in enumerate(b): if doll != 0: pop_arr[i].append(doll)
뽑은 인형을 저장할 bucket을 정의합니다.
bucket = []
뽑을 열을 찾고, 해당 열에서 인형을 뽑을 수 있는 상태인지 확인합니다.
뽑을 수 있는 경우라면, 인형을 위부터 뽑습니다.
for move in moves: move -= 1 if pop_arr[move]: doll = pop_arr[move].popleft() # deque를 사용한 경우 doll = pop_arr[move].pop() # board를 뒤집은 경우
bucket이 비어있지 않고, 현재 뽑은 인형과 동일한 인형이 맨 위에 존재한다면, 제거한 인형의 수를 증가시키면서 bucket 맨 위의 인형을 제거합니다.
그렇지 않다면, 인형을 bucket에 담습니다.
if bucket and bucket[-1] == doll: answer += 2 bucket.pop() else: bucket.append(doll)
더보기from collections import deque def solution(board, moves): answer = 0 n = len(board) pop_arr = [deque() for _ in range(n)] for b in board: for i, doll in enumerate(b): if doll != 0: pop_arr[i].append(doll) bucket = [] for move in moves: move -= 1 if pop_arr[move]: doll = pop_arr[move].popleft() if bucket and bucket[-1] == doll: answer += 2 bucket.pop() else: bucket.append(doll) return answer if __name__ == '__main__': result = solution( board=[[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]], moves=[1, 5, 3, 5, 1, 2, 1, 4] ) print(4 == result, result)
'Programmers' 카테고리의 다른 글
76501. 음양 더하기(Python, Programmers Level 1) (0) 2022.09.04 86051. 없는 숫자 더하기(Python, Programmers Level 1) (0) 2022.09.04 67256. [카카오 인턴] 키패드 누르기(Python, Programmers Level 1) (0) 2022.09.04 81301. 숫자 문자열과 영단어(Python, Programmers Level 1) (0) 2022.09.04 72410. 신규 아이디 추천(Python, Programmers Level 1) (0) 2022.09.04