[알고스팟] 쿼드 트리 뒤집기

https://algospot.com/judge/problem/read/QUADTREE

algospot.com :: QUADTREE

 

 

해설

분할정복을 이용한다. 각 구역은 4조각으로 나누면서 재귀를 호출한다. 재귀를 호출하면서 이미지를 상하 뒤집는다

서적에 나온대로 string을 매번 인덱스를 계산하는게 아니라 반복자를 이용하여 필요한 만큼 가져다 쓴다

 

lt : left top

rt : right top

lb : left bottom

rb : right bottom

def decompress(it):
    char = next(it, None)
    if char == None:
        return
    if char == 'b' or char == 'w':
        return char
    lt = decompress(it)
    rt = decompress(it)
    lb = decompress(it)
    rb = decompress(it)
    
    return 'x'+lb+rb+lt+rt

import sys

c = int(input().rstrip())
for _ in range(c):
    string = sys.stdin.readline().rstrip()
    slist = list(string)
    it = iter(slist)
    answer =  decompress(it)
    print(answer)