[python]2800_괄호 제거

1 걸린 시간 : 1h

2 사용한 자료구조 및 개념 : combinations, stack, set

---

💡 문제풀이 아이디어 및 어려웠던 점

 

💫 아이디어

    1️⃣ 괄호 짝들의 인덱스를 찾는다

    2️⃣ 짝 인덱스들을 모아 놓은 리스트와 combination을 사용하여 경우의 수를 구한다.

 

이상 자세한 설명은 주석 참고해주세요!

---

Solution Code & 주석

import sys
from itertools import combinations

string = sys.stdin.readline().rstrip()
idx_stack = []                           # 한 쌍의 괄호 인덱스들을 담을 스택 [['('의 인덱스, ')'의 인덱스], []]
brackets_stack = []                      # 괄호의 짝을 찾기 위한 스택, '('의 인덱스만 들어간다
answer = set()                           # 중복을 제거하기 위해 set 선언

for idx, v in enumerate(list(string)):   # enumerate를 사용해서 괄호와 해당 인덱스를 같이 뽑는다
    if v == '(':                         # 여는 괄호면 해당 인덱스를 brackets_stack에 append
        brackets_stack.append(idx)
    elif v == ')':                       # 닫는 괄호가 나왔으니 한 쌍이 이루어진 것
        start = brackets_stack.pop()     # 이 닫는 괄호의 짝의 인덱스를 start 변수에 담는다
        end = idx                        # 닫는 괄호의 인덱스는 end 변수에 담는다
        idx_stack.append([start, end])   # 짝을 이룬 괄호들읜 인덱스를 idx_stack에 넣는다

for i in range(1, len(idx_stack) + 1):   # 0의 경우는 input값 그대로니 1부터 시작한다
    for j in combinations(idx_stack, i): # 경우의 수 구하기 시작
        tmp = list(string)               # 괄호를 없애준 경우를 만들기 위해 임시 배열을 만든다. 기존 input값은 계속 사용해야하므로!
        for k in j:
            start, end = k
            tmp[start] = ''              # 괄호들을 공백으로 바꿔준다
            tmp[end] = ''
        answer.add(''.join(tmp))         # 공백을 제거한 배열을 담는다!
for i in sorted(list(answer)):
    print(i)

---