문제 요약
N x N 크기의 격자에 인형들이 쌓여 있고, 사용자는 크레인을 특정 열로 이동시켜 가장 위에 있는 인형을 뽑습니다.
뽑은 인형은 바구니에 순서대로 쌓입니다. 이때 바구니의 맨 위에 있는 인형과 새로 뽑은 인형의 모양이 같다면, 두 인형은 터지면서 사라집니다.
모든 크레인 동작이 끝난 뒤, 터져서 사라진 인형의 총 개수를 구하는 문제입니다.
입출력 예시
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]result = 4풀이 아이디어
이 문제의 핵심은 바구니를 스택으로 다루는 것입니다.
바구니에는 인형이 아래에서부터 쌓이지만, 실제로 비교해야 하는 대상은 항상 가장 마지막에 들어간 인형입니다. 따라서 리스트의 마지막 원소를 바구니의 맨 위 인형으로 생각하면 됩니다.
크레인이 한 번 움직일 때의 과정은 다음과 같습니다.
moves에 들어 있는 위치는 1번부터 시작하므로, 배열 인덱스로 사용하기 위해move - 1을 합니다.- 해당 열을 위에서 아래로 탐색하면서 0이 아닌 값을 찾습니다.
- 인형을 찾았다면 해당 칸을 0으로 바꿔 빈칸 처리합니다.
- 바구니가 비어 있지 않고, 바구니 맨 위 인형과 새 인형이 같다면
pop()으로 제거하고 정답에 2를 더합니다. - 다르다면 새 인형을 바구니에 넣습니다.
- 한 번의 크레인 동작에서는 인형 하나만 뽑을 수 있으므로
break로 탐색을 종료합니다.
Python 코드
def solution(board, moves):
answer = 0
basket = []
n = len(board)
for move in moves:
col = move - 1
for row in range(n):
doll = board[row][col]
if doll == 0:
continue
board[row][col] = 0
if basket and basket[-1] == doll:
basket.pop()
answer += 2
else:
basket.append(doll)
break
return answer코드 설명
basket = []바구니 역할을 하는 리스트입니다. 리스트의 마지막 원소가 바구니의 가장 위에 있는 인형입니다.
col = move - 1문제에서 크레인 위치는 1번부터 시작하지만, 파이썬 리스트 인덱스는 0부터 시작합니다. 따라서 1을 빼서 실제 열 인덱스로 변환합니다.
for row in range(n):
doll = board[row][col]선택한 열을 위에서 아래로 탐색합니다. 가장 먼저 만나는 0이 아닌 값이 현재 크레인으로 뽑을 수 있는 가장 위쪽 인형입니다.
if doll == 0:
continue0은 빈칸이므로 그냥 지나갑니다.
board[row][col] = 0인형을 뽑았으므로 해당 위치를 빈칸으로 바꿉니다.
if basket and basket[-1] == doll:
basket.pop()
answer += 2
else:
basket.append(doll)바구니 맨 위 인형과 새로 뽑은 인형이 같으면 두 인형이 터집니다. 이미 바구니에 있던 인형 하나를 pop()으로 제거하고, 새로 뽑은 인형까지 함께 사라지므로 answer에 2를 더합니다.
서로 다르면 새 인형을 바구니에 그대로 넣습니다.
시간 복잡도
board의 한 변 길이를 N, moves의 길이를 M이라고 하겠습니다.
크레인 동작 하나마다 최대 N개의 행을 탐색할 수 있습니다. 따라서 전체 시간 복잡도는 다음과 같습니다.
O(M * N)제한사항에서 N은 최대 30, M은 최대 1,000이므로 충분히 빠르게 동작합니다.
정리
이 문제는 격자에서 인형을 찾는 과정도 필요하지만, 핵심은 바구니에서 연속된 같은 인형을 처리하는 방식입니다.
바구니를 스택으로 생각하면 새 인형이 들어올 때마다 마지막 인형만 확인하면 되기 때문에 구현이 단순해집니다.
스택의 대표적인 활용 예시로도 좋은 문제입니다.
