올바른 괄호를 만들 때 가지치기를 어디에 둘지

길이 6짜리 올바른 괄호 문자열을 전부 찾는 문제다. 처음 짠 건 이렇다.

def do(cur=''):
    if len(cur) == 6:
        global li
        li.append(cur)
        return

    do(cur + '(')
    do(cur + ')')

자리마다 ( 와 ) 를 넣어 64개를 전부 만든다. 올바른지는 아직 안 본다. 만들고 나서 하나씩 검사하는 순서다.

만들면서 거른다

검사를 뒤로 미룰 이유가 없다. )))((( 같은 건 두 번째 글자에서 이미 틀렸는데 끝까지 만들고 있다.

열린 괄호가 몇 개 남았는지를 인자로 들고 다니면 된다.

def bin(n, x='', y=0):
    if y < 0: return

    if n == 0:
        if y == 0:
            print(x)
        return

    bin(n - 1, x + '(', y + 1)
    bin(n - 1, x + ')', y - 1)

bin(6)

y 는 아직 닫히지 않은 ( 의 개수다. ( 를 붙이면 1 늘고 ) 를 붙이면 1 준다.

두 군데에서 걸러낸다.

• y < 0 이면 그 자리에서 돌아간다. 닫는 괄호가 여는 괄호보다 많아진 순간이고, 여기서 더 붙여봐야 절대 복구되지 않는다.
• 다 만든 시점에 y == 0 이어야 한다. 남은 게 있으면 짝이 안 맞는다.

첫 번째가 가지치기고 두 번째는 마지막 검사다. 앞의 것을 앞으로 당긴 만큼 만들지 않는 가지가 생긴다.

8개월쯤 지나 같은 문제를 다시 풀었을 때도 같은 형태로 썼다. 이름과 인자 순서만 바뀌었다.

def rec(cur="", status=0):
    if status < 0:
        return

    if len(cur) == n * 2:
        if status == 0:
            ans.append(cur)
        return

    rec(cur + "(", status + 1)
    rec(cur + ")", status - 1)

앞의 답에서 다음 답을 만들 수 있을까

n=5의 답을 다 구해놓고 나서, 거기서 n=6의 답을 만들어낼 수 있는지 확인해봤다. 규칙은 세 가지로 잡았다.

new = []
for i in five:
    new.append("()" + i)
    new.append(i + "()")
    new.append("(" + i + ")")

앞에 () 를 붙이거나, 뒤에 붙이거나, 통째로 감싸는 것이다.

six_set = set(six)
test_set = set(new)

for i in (six_set - test_set):
    print(i)

차집합이 비어 있으면 이 세 규칙으로 전부 만들어진다는 뜻이다. 132개 중 20개가 남았다. ((()))((())) 처럼 가운데에서 둘로 갈라지고 양쪽이 다 두 겹 이상인 것들이다. 앞이나 뒤에 () 를 붙이는 것으로는 한쪽이 반드시 () 가 되고, 통째로 감싸면 갈라지지 않는다.

n=5의 답 42개와 n=6의 답 132개를 직접 만들어놓고 집합 연산으로 확인한 것이라, 코드는 짧지만 답이 확실하다.