알고스팟 : 쿼드 트리 뒤집기 (분할정복)

 

 

이미 압축되어 출력된 부분을 다시 원래 모양대로 풀고 나서 뒤집고 다시 압축하려고 하면 초과가 발생하는 문제이다. 이미 압축되어있는 버전에서 부분 별로 위와 아래만 바꿔주도록 적용해야 한다. 

 

c = int(input())

def reverse(s, idx):
    if s[idx] == 'w' or s[idx] =='b' :
        return s[idx]
    # x로 시작한다는 의미이므로 한칸 앞으로 
    idx +=1 
    upperLeft = reverse(s, idx)
    idx += len(upperLeft)
    upperRight = reverse(s, idx)
    idx += len(upperRight)
    lowerLeft = reverse(s, idx)
    idx += len(lowerLeft)
    lowerRight = reverse(s, idx)
    return  "x" + lowerLeft + lowerRight + upperLeft + upperRight

for case in range(c) :
    s = input() 
    print(reverse(s, 0))