백준 #2800 괄호 제거

코드

import sys
sys.stdin = open("input.txt")
input = sys.stdin.readline


def solve(idx, result):
    if idx == n:
        if result:
            equation = ""
            for i in range(len(arr)):
                if i not in result:
                    equation += arr[i]
            answer.append(equation)
        return

    solve(idx + 1, result + pairs[idx])
    solve(idx + 1, result)
    
    return


arr = list(input().rstrip())
stack = []
pairs = []
for i in range(len(arr)):
    if arr[i] == "(":
        stack.append(i)
    elif arr[i] == ")":
        pairs.append((stack.pop(), i))
n = len(pairs)
answer = []

solve(0, ())
answer = sorted(set(answer))
for x in answer:
    print(x)

풀이

먼저 스택을 이용하여 짝이 맞는 괄호들의 인덱스를 pairs라는 곳에 저장해주었다. 브루트포스 알고리즘으로 전체 경우의 수를 구해주어 answer라는 배열에 가능한 정답들을 저장해주었다. 처음에 틀렸었는데 이유는 괄호가 ((7777)) 이런식으로 있는 경우에 바깥괄호를 지운것과 안쪽 괄호를 지운 결과가 같기 때문에 중복제거를 해주어야 하기 때문이다. set으로 중복제거를 해준 후에 정렬을 해주어 출력해주었다.