[python] 1차원 뿌요뿌요

문제

뿌요뿌요는 여러 색깔의 뿌요(블럭)들을 적절히 배치하여, 가능한 많은 뿌요를 터트리는 것이 목적인 낙하형 퍼즐 게임이다. 원래 게임은 2차원 보드에서 진행이 되지만 이 문제는 1차원 보드라고 가정하자.

 

현재 보드 위에 N개의 뿌요가 늘어선 상태이며, 같은 색깔의 뿌요가 M개 이상 서로 붙어 있으면 터진다. 여러 뿌요가 동시에 터지는 조건을 만족할 때는 그 중 가장 왼쪽에 있는 뿌요들이 터지기 시작한다.

 

보드의 초기 상태를 나타낸 문자열이 주어졌을 때, 더 이상 뿌요가 터지지 않게 되었을 때 보드의 상태를 구해보자.

 

 

예제 설명

처음 보드의 상태는 ABCCBCCDA 이고 2개가 붙어있을 경우 터진다고 가정하자.

처음 뿌요가 터짐에 따라 ABBCCDA, ACCDA, ADA 순서로 보드의 상태가 변하게 된다.

 

 

입력

첫째 줄에 두 정수 N, M이 공백을 두고 주어진다.

둘째 줄에 길이 N의 뿌요 문자열 S가 주어진다. 뿌요 문자열의 각 문자는 해당 위치에 놓여있는 뿌요의 색깔을 의미한다.

• 2 ≤ M ≤ N ≤ 200,000
• S는 알파벳 대문자로만 이루어진 문자열이다.

 

 

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
s = input().rstrip()

resultStack = []
resultStack.append(['', 1])  # 첫 뿌요를 확인하기 위한 더미데이터

s += 'a'  # 마지막 뿌요가 터저야 할지 말지 판단하기 위한 더미데이터
for c in s:
	if resultStack[-1][0] != c:
		if resultStack[-1][1] >= m:
			bbooYoPop = resultStack[-1][0]
			while bbooYoPop == resultStack[-1][0]:
				resultStack.pop()
	
	if resultStack[-1][0] == c:
		resultStack.append([c, resultStack[-1][1] + 1])
	else:
		resultStack.append([c, 1])

resultStack.pop()

if len(resultStack) > 1:
	print(''.join(resultStack[i][0] for i in range(len(resultStack))))
else:
	print("CLEAR!")

뿌요가 해당 갯수 이상이 되면 터져야 함을 잊고 구현했다가 한참 고생했던 문제이다.

그리고 스택을 활용하여 [현재뿌요, 연속된개수]로 한다는 아이디어는 처음 봐서 분명 언젠가 또 써먹을 아이디어라고 생각한다.

 

 

 

※출처

https://multicampus-kdt.goorm.io/lecture/38996/멀티잇-코딩테스트-러닝클래스-python-6월반