[백준 2800 괄호 제거 문제] PYTHON

 

골드 5문제지만 최근 풀었던 것 중 가장 시간이 오래걸렸다..

히든 케이스를 찾느라 오래걸리기도 했고 itertools의 combinations를 몰라

더럽게 코딩을 할까 고민을 하며 찾아보다 combinations를 찾아 시간이 더 오래걸렸다.

이번 문제는 우선 문자열을 list로 변환하고 괄호의 짝을 찾아 표시를 했다.

예를 들어 [(,1,+,(,2,+,1,),)] 이라하면[1,0,0,2,0,0,0,2,1] 이런식으로 먼저 짝을 찾은 후

각각의 짝을 인덱스로 묶었다. 위를 예로 들어 [(0,8),(3,7)] 이런식으로

그 후 해당 리스트를 combinations를 사용해 모든 경우를 찾았다.

나는 괄호를 지우는 case를 찾아 [[(0,8)],[(3,7)],[(0,8),(3,7)]] 이렇게 나온다.

이걸 for문을 통해 괄호로 지우면 끝난다.

 

import itertools
ina = input()
count = 1
lenina = len(ina)
arrina = [0]*lenina
stacknum = []
stacknum2 = []
where = []
for i, arr in enumerate(ina):
    if arr == '(':
        arrina[i] = count
        stacknum.append(count)
        stacknum2.append(i)
        count += 1
    elif arr == ')':
        arrina[i] = stacknum.pop()
        where.insert(0, [i, stacknum2.pop()])
count -= 1

answer = []
case = []
for i in range(1, count+1):
    case.extend(list(itertools.combinations(where, i)))
for cas in case:
    tmpina = list(ina)
    for ca in cas:
        for c in ca:
            tmpina[c] = ' '
    answer.append(''.join(tmpina).replace(" ", ""))
answer = set(answer)
answer = list(answer)
for ai in sorted(answer):
    print(ai)