백준 2800 [괄호 제거] 파이썬

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

2800번: 괄호 제거

# 백준 2800 괄호 제거
import sys
from itertools import combinations
input = sys.stdin.readline
lst = list(map(str, input().rstrip()))
stack = []
arr = []
for i in range(len(lst)):
    if lst[i] == '(':
        stack.append(i)
    elif lst[i] == ')':
        k = stack.pop()
        arr.append([k, i])
# arr.sort()
ans = []
for i in range(1, len(lst)+1):
    comb = combinations(arr, i)
    for c in comb:
        sol = ''
        temp = list(map(str, lst))
        for val in c:
            temp[val[0]] = '?'
            temp[val[1]] = '?'
        for val in temp:
            if val != '?':
                sol += val
        ans.append(sol)
ans.sort()
dup = []
for val in ans:
    if not val in dup:
        dup.append(val)
        print(val)

 

 

 

괄호쌍의 좌표를 저장하고, combination을 돌려서 모든 경우의 수를 계산한다. (괄호가 최대 10개 밖에 없으므로 가능하다.) 그리고 없앨 괄호 자리에 '?'를 넣고, 이를 무시한 문자열을 생성한다.

<중요> 중복을 제거한다.

((1)) 이면, 첫번째 괄호쌍을 제거한 (1) 두번째 괄호쌍을 제거한 (1) 경우가 같으므로 중복을 제거한다.