문제 링크

접근 방법

문제를 처음 봤을 때 괄호를 하나씩 없애면 되지 않을까 생각했다.

1. 괄호의 index 값을 전부 찾는다.
2. 스택을 이용해 괄호의 짝을 맞춰 저장한다.
3. 재귀함수를 통해 해당 괄호를 넣을지 말지 결정한다.

마지막으로 괄호가 전부 있게되는 경우만 빼주면 원하는 값을 얻을 수 있었다. 총 개수는 2^n-1개가 나온다.

풀다가 2번 막혔는데 다른 분의 풀이를 참고해서 개선했다.
최종 풀이의 흐름은 다음과 같다.

1. 괄호의 index 값에 괄호번호를 부여한다.
2. 재귀함수를 통해 모든 경우의 수를 확인한다.

---

1. 괄호의 index 값에 괄호번호를 부여한다.

val = input().rstrip()
stack = []
index = [-1 for _ in range(len(val))]
curr_num = 0

for idx, ch in enumerate(val):
    if ch == '(':
        index[idx] = curr_num
        stack.append(idx)
        curr_num += 1
    elif ch == ')':
        index[idx] = index[stack.pop()]

a. 초기 index값은 전부 -1로 설정한다.
b. 만약 값이 (라면 index 값을 현재 괄호번호인curr_num으로 지정한다.
c. stack을 활용하여 여는괄호와 닫는괄호의 index값을 일치하게 만든다.

예를 들어
(2+(2*2)+2)
를 변경한다고 하면 괄호가 위치한 index값을 아래와 같이 맞춰줄 수 있다.
[0, -1, -1, 1, -1, -1, -1, 1, -1, -1, 0]

2. 재귀함수를 통해 모든 경우의 수를 확인한다.

choose = [0 for _ in range(curr_num)]
answers = []

def find_answers(cnt):
    if cnt == curr_num:
        if sum(choose) == 0:
            return

        answer = ""
        for idx, ch in enumerate(val):
            if index[idx] == -1 or choose[index[idx]] == 0:
                answer += ch
        answers.append(answer)
        return

    choose[cnt] = 1
    find_answers(cnt + 1)
    choose[cnt] = 0
    find_answers(cnt + 1)


find_answers(0)

a. cnt == curr_num일 경우 포함유무에 대한 결정은 끝났다.
b. 만약 choose가 모두 0일경우 모두 선택이 된 경우이니 패스한다.
c. 초기 입력값에 대해서 -1은 문자이므로 넘기고, choose 값이 0일 경우 선택된 괄호이므로 추가해준다.

    choose[cnt] = 1
    find_answers(cnt + 1)
    choose[cnt] = 0
    find_answers(cnt + 1)

이 부분에 대해서는 1일 경우 선택하지 않고, 0일 경우 선택하므로 각각의 경우에 대해서 재귀를 돌게 된다.

이렇게 저장한 answer을 출력해주면 된다.

최종 코드

import sys

input = sys.stdin.readline

val = input().rstrip()
stack = []
index = [-1 for _ in range(len(val))]
curr_num = 0

for idx, ch in enumerate(val):
    if ch == '(':
        index[idx] = curr_num
        stack.append(idx)
        curr_num += 1
    elif ch == ')':
        index[idx] = index[stack.pop()]

print(index)

choose = [0 for _ in range(curr_num)]
answers = []


def find_answers(cnt):
    if cnt == curr_num:
        if sum(choose) == 0:
            return

        answer = ""
        for idx, ch in enumerate(val):
            if index[idx] == -1 or choose[index[idx]] == 0:
                answer += ch
        answers.append(answer)
        return

    choose[cnt] = 1
    find_answers(cnt + 1)
    choose[cnt] = 0
    find_answers(cnt + 1)


find_answers(0)
answers = sorted(set(answers))
print('\n'.join(answers))