[백준] Python - 2800 괄호 제거

문제 링크

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

2800번: 괄호 제거

 

문제 풀이

1. ()의 쌍을 찾는다. (ex. "(0/(0))"의 경우 [(3, 5), (0, 6)])
2. 조합으로 모든 경우의 수를 찾는다.
3. 경우의 수에 따라 for 문을 돌면서 해당 자리를 비우고, result에 추가한다. 
4. 정렬하여 출력한다.

 

전체 코드

from itertools import combinations

expression = input().strip()
pair = []
temp = []
result = set()

for index, word in enumerate(expression) :
    if word == '(' :
        temp.append(index)
    elif word == ')' :
        pair.append((temp.pop(), index))

for i in range(1, len(pair)+1) :
    cases = combinations(pair, i)

    for j in cases :
        ex = list(expression)
        for (start, end) in j :
            ex[start] = ""
            ex[end] = ""

        result.add(''.join(ex))

for r in sorted(list(result)):
    print(r)