괄호 제거(백준 2800번)

문제

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

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

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

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

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

나의 풀이(정답 참고)

from itertools import combinations

In=list(input())
stack=[]
bracket_list=[]
for i in range(len(In)):
    if In[i]=='(':
        stack.append(i)
    elif In[i]==')':
        bracket_list.append((stack.pop(),i))
exp_list=set()
for i in range(1,len(bracket_list)+1):
    for c in combinations(bracket_list,i):
        tmp=list(In)
        for j in range(i):
            tmp[c[j][0]]=''
            tmp[c[j][1]]=''
        exp_list.add(''.join(tmp))
exp_list=sorted(list(exp_list))
for exp in exp_list:
    print(exp)

• 먼저 괄호의 위치를 파악하여, 쌍을 이루는 괄호의 index정보를 튜플형태로 list에 모두 저장한다.
• 그 후, 괄호 쌍들을 저장한 bracket_list의 모든 조합을 itertools라이브러리의 combinations로 구한다.

주의) exp_list.add(''.join(tmp))

여기서 exp_list를 원래 list로 선언해서, append로 넣어주었는데, exp_list는 set()이어야 한다.

⇒ 만약 ((1+2))라는 식이 있을 때, 어떠한 괄호 쌍을 없애도 (1+2), (1+2)이기 때문

---

추가적인 문법

• from itertools import combinations
  • 조합을 구해주는 라이브러리 함수
• set()은 중복되는 값이 없다.(집합 자료형이기 때문에 겹치는 값이 없음)
  • set.add()로 값을 추가할 수 있다.
  • set.update() 여러개의 값을 추가

    >>> s1 = set([1, 2, 3])
    >>> s1.update([4, 5, 6])
    >>> s1
    {1, 2, 3, 4, 5, 6}
  

  • set.remove() 특정값을 제거할 때 사용

    >>> s1 = set([1, 2, 3])
    >>> s1.remove(2)
    >>> s1
    {1, 3}
  

  • 교집합

    >>> s1 & s2
    {4, 5, 6}
  

  • 합집합

    >>> s1 | s2
    {1, 2, 3, 4, 5, 6, 7, 8, 9}
  

  • 차집합

    >>> s1 - s2
    {1, 2, 3}
    >>> s2 - s1
    {8, 9, 7}