[BAE/<JOON>][백준][#8913] 문자열 뽑기

 

https://www.acmicpc.net/problem/8913

8913번: 문자열 뽑기

문제

a와 b로만 이루어진 문자열 s이 있다. 그룹은 같은 글자로 이루어진 가장 긴 연속 부분 문자열이다. 길이가 2 이상인 s의 모든 그룹 g는 제거할 수(뽑을 수) 있고, 남은 왼쪽 부분과 오른쪽 부분을 연결해서 새 문자열을 만들 수 있다. 이러한 과정은 문자열이 빈 문자열이 되거나, 길이가 2 이상인 그룹이 없을 때 까지 계속한다.

예를 들어, s = babbbaaabb일 때, s에는 그룹이 다섯 개 있다. s는 다음과 같은 단계를 거쳐서 빈 문자열로 바꿀 수 있다. (밑 줄이 그어져 있는 그룹이 뽑히는 그룹)

babbbaaabb → baaaabb → bbb → 빈 문자열

하지만, 아래와 같은 단계를 거친다면, 빈 문자열로 바꿀 수 없다.

babbbaaabb → babbbaaa → baaaa → b

문자열이 주어졌을 때, 적절한 과정을 거쳐 빈 문자로 바꿀 수 있는지 없는지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 a와 b로 이루어진 문자열로 이루어져 있다. 문자열의 길이는 1보다 크거나 같고, 25보다 작거나 같다.

출력

각 테스트 케이스에 대해서, 입력으로 주어진 문자열을 빈 문자열로 바꿀 수 있으면 1을, 없으면 0을 출력한다. 

 

예제 입력	예제 출력
3 babbbaaabb aabbaabb abab	1 1 0

 

---

 

문자열의 최대 길이가 25자이므로, 재귀로 모든 케이스에 대해 다 돌려도 시간 초과는 발생하지 않을 것 같다.

하나씩 하나씩 지워가다 되는 경우가 있으면 1 리턴하고 끝내 버리자.

(python의 regex를 이용하여 연속된 문자(group)을 간편하게 찾자!)

 

 Python3

import re

def solve(s):
    group = [(m.start(0), m.end(0)) for m in re.finditer('aa+|bb+', s)]
    if len(group) == 0: return 0
    if len(set(s)) == 1: return 1
    for g in group:
        if solve(s[0:g[0]] + s[g[1]:]) == 1: return 1
    return 0

strings = [input() for _ in range(int(input()))]
for string in strings:
    print(solve(string))