https://www.acmicpc.net/problem/2800

---

1. 코드

import sys
from collections import defaultdict

def dfs(index, path):
    if len(path) > 0:
        result.append(sorted(path[:]))
    for i in range(index, len(arr)):
        dfs(i + 1, path + [arr[i]])


exp = sys.stdin.readline().rstrip()
d = defaultdict(int)
count = 1
stack = []
for idx, char in enumerate(exp):
    if char == '(':
        stack.append(idx)
    elif char == ')':
        start = stack.pop()
        end = idx
        d[count] = (start, end)
        count += 1
arr = list(range(1, len(d) + 1))
result = []
dfs(0, [])
answer = []
for i in result:
    temp = list(exp)
    # 제외할 괄호의 위치를 'x'로 표시한다.
    for j in i:
        x, y = d[j]
        temp[x] = temp[y] = 'x'
    temp_result = ''
    for k in temp:
    	# 제외할 괄호('x')가 아니라면 추가
        if k != 'x':
            temp_result += k
    # 테스트케이스
    if temp_result not in answer:
        answer.append(temp_result)
answer.sort()
for i in answer:
    print(i)

---

2. 코드 설명

예시) exp = '(1+(2*(3+4)))'
예시) result = [[1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

• def dfs(index, path): [LeetCode] Subsets 해설 참조

• d = defaultdict(int): 입력값 안에 위치한 괄호 쌍의 인덱스가 튜플 형태로 존재한다.
  d[1]=(6, 10) d[2]=(3, 11) d[3]=(0, 12)

• result: 각 1차원 리스트에는 제거해야 하는 괄호 쌍의 조합이 들어있다.
  만약 result에서 현재 순서가 [1,2] 라면, 문자열의 d[1]과 d[2]에 해당하는 인덱스를 제거한 문자열이 temp_result에 담기게 된다.

코드 풀이

1. dfs를 통해 모든 경우의 수를 result 에 추가한다.

2. for 문으로 result 를 탐색한다. 각 경우에 해당하는 결과값은 temp_result로 받아서 answer에 추가한다.

3. 마지막 answer.sort()를 통해 답을 정렬한다.

테스트케이스

예시) exp='(((1)))(2)'

처음 만나는 3개의 괄호 쌍 중 하나만 제거하는 경우, 어떤 괄호를 제거하든 모든 입력값은 동일한 형태이기 때문에 중복된 값이 answer에 추가될 수 있다.
if temp_result not in answer:를 추가하여 중복 추가를 방지할 수 있다.