괄호제거

출처 : 백준 #2800

시간 제한	메모리 제한
1초	128MB

---

문제

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

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

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

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

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

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

---

입력

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

---

출력

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

---

입출력 예시

예제 입력 1

(0/(0))

예제 출력 1

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

---

예제 입력 2

(2+(2*2)+2)

예제 출력 2

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

---

예제 입력 3

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

예제 출력 3

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

---

풀이

생각

• (가 나올 때 임시 스택인 r에 쌓아두다가 )가 나오면 pop하여 괄호 쌍을 모으는 리스트인bracket에 튜플 형태로 넣어주었다.
• 이를 combinations를 사용하여 가능한 조합의 쌍을 만들고 그 쌍 안에 있는 인덱스에 해당이 되면 괄호를 "" 빈문자열로 바꿔준 뒤 join하였다.
• 중복을 제거하기 위해 result를 처음엔 집합 자료구조를 사용하였고, 원소를 다 받고 나서는 리스트로 변경하여 사전순 정렬을 해주었다.
  

python code

# 백준 2800번 괄호 제거
from sys import stdin
from itertools import combinations
input = stdin.readline

string = list(input().rstrip())
r = []
bracket = []
for i in range(len(string)):
    if string[i] == "(":
        r.append(i)
    elif string[i] == ")": 
        bracket.append((r.pop(), i))                      

result = set()  # 중복 제거용
for i in range(1, len(bracket)+1):
    comb = list(combinations(bracket, i))  # 제거할 괄호의 쌍 구하기
    for c in comb:
        temp = string[:]
        for s, e in c:
            temp[s] = ""
            temp[e] = ""
        result.add("".join(map(str, temp)))
    
result = list(result)
result.sort()
for i in range(len(result)):
    print(result[i])