[BOJ] 백준 파이썬 > 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개이다. 

출력

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

 

입출력 예제

출처 : 백준 2800번 괄호 제거

2800번: 괄호 제거

---

나의 풀이 in Python

from itertools import combinations
problem = [*input().strip()] # 문자열 하나씩 리스트화
p, idx_brs = [],[]
# 짝이 맞는 괄호의 위치 idx_brs에 저장해줌
for i,v in enumerate(problem):
    if v == '(':problem[i] ='';p+=[i]
    if v == ')':problem[i] ='';idx_brs +=[[p.pop(),i]]
# print(idx_brs)
out = set()
# 짝이 맞는 괄호 위치를 조합을 통해 조정해줌
for i in range(len(idx_brs)):
    for j in combinations(idx_brs,i):
        P = problem[:]
        # print(P)
        for v,w in j:
            P[v] = '('
            P[w] = ')'
        out.add(''.join(P))
for i in sorted(out):print(i)

짝이 맞게 제거한 괄호 위치의 경우의 수를 구하라는 문제였습니다.

처음에는 쉬운 난이도의 문제인 줄 알았는데 저에게는 조금 높은 난이도의 문제였던 것 같습니다.

 

주석에 설명을 달아놨는데 핵심은 짝이 맞는 괄호의 위치를 idx로 리스트화해주고 이에 대한 경우의 수를 combinations를 이용하여 푸는 것이었습니다.