[백준] 2800번 괄호제거

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

2800번: 괄호 제거

문제

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

이 수식은 괄호가 올바르게 쳐져 있다. 예를 들면, 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개이다. 

 

출력

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

 

 

 

풀이

괄호의 위치를 저장한 뒤 조합을 이용해서 만들 수 있는 괄호의 위치들을 선택하면 된다.

 

전체 코드

import sys
import itertools

expression = list(map(str, sys.stdin.readline().strip()))
stack, pos, answer = [], [], set()

for i, value in enumerate(expression):
    if value == '(':
        stack.append(i)
    if value == ')':
        pos.append((stack.pop(), i))

for i in range(1, len(pos)+1):
    comb = itertools.combinations(pos, i)
    for j in comb:
        temp = expression[:]
        for s, e in j:
            temp[s] = ''
            temp[e] = ''
        answer.add(''.join(map(str, temp)))
for i in sorted(list(answer)):
    print(i)

괄호를 1개부터 N개까지 제거하는 방법으로 구현하였다.
괄호의 위치를 pos 리스트에 저장한 뒤 combinations을 이용하여 조합을 구현해서
해당 위치의 괄호를 제거했다.