[백준] 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

풀이

---

from itertools import combinations
import sys

input = sys.stdin.readline

s = input().rstrip()

l = []
stack = []
answer = set()

for idx, v in enumerate(list(s)):
    if v == '(':
        stack.append(idx)
    elif v == ')':
        start = stack.pop()
        end = idx
        l.append([start,end])

for i in range(1,len(l)+1):
    combi = combinations(l,i)
    for j in combi:
        tmp = list(s)
        for k in j:
            start,end = k
            tmp[start] = ''
            tmp[end] = ''
        answer.add(''.join(tmp))


for i in sorted(list(answer)):
    print(i)

정리

---

• 입력되는 문자열을 for문을 통해 돌면서 '('와')'의 쌍의 위치를 저장하고, 저장된 배열을 조합을 통해 제거 할 위치들을 뽑아 제거했다.