[백준] 괄호제거(2800) - python

문제

어떤 수식이 주어졌을 때, 괄호를 제거해서 나올 수 있는 서로 다른 식의 개수를 계산하는 프로그램을 작성하시오.

이 수식은 괄호가 올바르게 쳐져 있다. 예를 들면, 1+2, (3+4), (3+4*(5+6))와 같은 식은 괄호가 서로 쌍이 맞으므로 올바른 식이다.

하지만, 1+(2*3, ((2+3)*4 와 같은 식은 쌍이 맞지 않는 괄호가 있으므로 올바른 식이 아니다.

괄호를 제거할 때는, 항상 쌍이 되는 괄호끼리 제거해야 한다.

예를들어 (2+(2*2)+2)에서 괄호를 제거하면, (2+2*2+2), 2+(2*2)+2, 2+2*2+2를 만들 수 있다. 하지만, (2+2*2)+2와 2+(2*2+2)는 만들 수 없다. 그 이유는 쌍이 되지 않는 괄호를 제거했기 때문이다.

어떤 식을 여러 쌍의 괄호가 감쌀 수 있다.

입력

첫째 줄에 음이 아닌 정수로 이루어진 수식이 주어진다. 이 수식은 괄호가 올바르게 쳐져있다. 숫자, '+', '*', '-', '/', '(', ')'로만 이루어져 있다. 수식의 길이는 최대 200이고, 괄호 쌍은 적어도 1개, 많아야 10개이다. 

출력

올바른 괄호 쌍을 제거해서 나올 수 있는 서로 다른 식을 사전 순으로 출력한다.

예제 입력 1 

(0/(0))

예제 출력 1 

(0/0)
0/(0)
0/0

예제 입력 2 

(2+(2*2)+2)

예제 출력 2 

(2+2*2+2)
2+(2*2)+2
2+2*2+2

예제 입력 3 

(1+(2*(3+4)))

예제 출력 3 

(1+(2*3+4))
(1+2*(3+4))
(1+2*3+4)
1+(2*(3+4))
1+(2*3+4)
1+2*(3+4)
1+2*3+4

 

---

모르겠어서 다른 사람 코드 참고함

<코드>

import sys
from itertools import combinations
input = sys.stdin.readline
answer = []
stack = []
result = set()

arr = list(input())

for i in range(len(arr)):
    if arr[i] == '(':
        stack.append(i)   
    elif arr[i] == ')':
        answer.append((stack.pop(), i))

for i in range(len(answer)):
    for j in combinations(answer, i+1):
        tmp = arr[:]
        for idx in j:
            tmp[idx[0]] = tmp[idx[1]] = ''
        result.add("".join(tmp))
        
for item in sorted(result):
    print(item)

1. answer에 괄호쌍의 인덱스를 저장한다

2. 인덱스 쌍의 조합을 구한다

ex) (1+(2*(3+4)))일때 answer에는 (0, 12), (3, 11), (6, 10)이 있으니까 괄호를 제거할 수 있는 조합은 다음과 같다.
((6, 10),)
((3, 11),)
((0, 12),)
((6, 10), (3, 11))
((6, 10), (0, 12))
((3, 11), (0, 12))
((6, 10), (3, 11), (0, 12))

3. 해당 인덱스 부분의 괄호를 제거한다. -> ''로 대체함. del이나 remove로 지우면 인덱스가 바뀌기 때문에 처음 인덱스를 유지하기 위해 공백으로 대체했다.

그러면 tmp는 

['(', '1', '+', '(', '2', '*', '', '3', '+', '4', '', ')', ')', '\n']
['(', '1', '+', '', '2', '*', '(', '3', '+', '4', ')', '', ')', '\n']
['', '1', '+', '(', '2', '*', '(', '3', '+', '4', ')', ')', '', '\n']
['(', '1', '+', '', '2', '*', '', '3', '+', '4', '', '', ')', '\n']
['', '1', '+', '(', '2', '*', '', '3', '+', '4', '', ')', '', '\n']
['', '1', '+', '', '2', '*', '(', '3', '+', '4', ')', '', '', '\n']
['', '1', '+', '', '2', '*', '', '3', '+', '4', '', '', '', '\n']

4. "".join(tmp)해서 합쳐주기