[백준] 2800. 괄호 제거/Python - Gold4

❓문제

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

성능 요약

 

메모리: 32412 KB, 시간: 36 ms

분류

비트마스킹, 브루트포스 알고리즘, 자료 구조, 스택, 문자열

 

문제 설명

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

이 수식은 괄호가 올바르게 쳐져 있다. 예를 들면, 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)는 만들 수 없다. 그 이유는 쌍이 되지 않는 괄호를 제거했기 때문이다.

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

✍🏻풀이

우리는 항상 쌍이 되는 괄호끼리 제거해야 한다. 그러므로 먼저 괄호의 쌍을 찾아야 한다. '('이 나오면 스택에 '('의 위치를 넣는다. 그리고 ')'이 나오면 쌍을 찾았으므로 스택 가장 위의 '('의 위치와 ')'의 위치를 다른 리스트에 넣는다. 이러한 방식으로 쌍을 찾으면 된다.

쌍을 찾았으면 괄호를 제거하여 나올 수 있는 식의 개수를 구해야 한다. 만약 괄호의 위치가 (0, 10), (3, 7)이 있다고 해보자. 그럼 우리는 (0, 10)만 제거해도 되고, (3, 7)에 있는 괄호만 제거해도 된다. 혹은 둘 다 지울 수도 있다. 이는 조합으로 combinations 라이브러리를 사용해서 구하면 된다. 그리고 이렇게 나온 조합을 이용하여 지우고자 하는 위치를 빈칸으로 바꾸면 괄호가 제거된 식이 나온다. 마지막으로 나온 식들을 정렬해서 출력하면 된다.

💻코드

import sys
from itertools import combinations

input = sys.stdin.readline

S = list(input().strip())
st = []
indices = []

res = set()
for i in range(len(S)):
    if S[i] == '(':
        st.append(i)
    elif S[i] == ')':
        indices.append((st.pop(), i))

for i in range(len(indices)):
    for comb in combinations(indices, i+1):
        temp = S[:]
        for c in comb:
            temp[c[0]] = temp[c[1]] = ""
        res.add("".join(temp))

for s in sorted(list(res)):
    print(s)

📍후기

머리로 이해해도 코드로 만드는 것은 어렵다...