[코딩 테스트 연습(파이썬/Python)] 백준(BOJ) 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개이다. 

[출력]

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

 

[아이디어]

1) 괄호의 쌍 위치를 인덱스로 구해놓는다.

2) 1)에서 구한 배열로 멱집합(powerset)을 구성한다. (공집합 제외)

3) 해당 위치의 괄호들을 모두 ""로 바꾼 문자열을 정답 목록에 추가한다.

4) 정렬하여 출력

s=input()
s1 = []
s2 = []
ind = []
for i, x in enumerate(s):
    if x=='(':
        s1.append(x)
        s2.append(i)
    if x==')':
        if s1[-1]=="(":
            s1.pop()
            ind.append((s2.pop(),i))

pow_ = []
n = len(ind)
for i in range(1,2**n):
    flag = bin(i)[2:].zfill(n)
    subset = [ind[j] for j in range(n) if flag[j] == '1']
    pow_.append(subset)

def sub(x,s):
    i,j = x
    return s[:i] + "a" + s[i+1:j] + "a" + s[j+1:]

ans = set()
for x in pow_:
    s_ = s
    for y in x:
        s_ = sub(y,s_)
    ans.add(s_.replace("a", ""))

print(*sorted(list(ans)), sep = '\n')

멱집합(powerset)을 구할 때 이진수를 이용한 다른 사람의 코드를 활용했다. 저렇게 하지 않고 1부터 n까지의 combination을 모두 구하는 방법도 있다. 문자열 중 ""이 되어야 하는 부분을 다 'a'로 바꿔두고 마지막에 ""로 변경했는데, 리스트화 해서 해당 인덱스 위치의 ""로 바꾸는 방법도 있다.

다른 풀이는 아래.

from itertools import*
s,l,q=[*input()],[],[]
for i,v in enumerate(s):
    if v=='(':
        s[i]='';l+=[i]
    if v==')':
        s[i]='';q+=[[l.pop(),i]]
p=set()
for i in range(len(q)):
    for c in combinations(q,i):
        S=s[:]
        for v,w in c:
            S[v],S[w]='(',')'
        p.add(''.join(S))
for i in sorted(p):
    print(i)