백준 2800번 괄호제거 (python)

Problem

2800번: 괄호 제거

Solution

import sys

exp = sys.stdin.readline().strip()
answer = set()

def dfs(idx, stack, expression):
    # end condition
    if idx >= len(exp):
        if expression != exp:
            answer.add(expression)
        return

    curr = exp[idx]

    if curr == "(":
        # ( 제외
        stack_1 = stack + [False]
        dfs(idx+1, stack_1, expression)

        # ( 포함
        stack_2 = stack + [True]
        expression += curr
        dfs(idx+1, stack_2, expression)

    else:
        if curr == ")":
            if stack.pop():
                expression += curr

        else:
            expression += curr

        dfs(idx+1, stack, expression)

dfs(0, [], "")
for e in sorted(answer):
    print(e)

“(”이 나오면 True 또는 False를 stack에 넣었다. 이를 통해 매칭되는 “)”의 출력 여부를 결정하였다.

Reference