백준(BAEKJOON) 2800 괄호제거 - Python

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

2800번: 괄호 제거

 

 

풀이

from itertools import combinations

# 사용자 입력 받기
n = list(input())  # 사용자로부터 입력받은 수식을 문자열 리스트로 변환.
stack = []  # 괄호 쌍의 시작 인덱스를 판별
array = []  # 괄호 쌍의 인덱스를 저장.
answer = []  # 괄호를 제거한 후의 모든 가능한 식을 저장용도

# 괄호 쌍 위치 찾기
for i in range(len(n)):
    if n[i] == '(':  # 여는 괄호를 찾으면 스택에 인덱스를 추가
        stack.append(i)
    elif n[i] == ')':  # 닫는 괄호를 찾으면 스택에서 가장 최근의 여는 괄호 인덱스를 꺼내고
        s = stack.pop()  # 여는 괄호와 닫는 괄호의 인덱스 쌍을 array에 추가.
        array.append([s, i])

# 괄호 쌍을 제거하는 모든 조합 찾기
for i in range(1, len(array) + 1):
    for combo in combinations(array, i):  # array의 모든 가능한 조합을 생성
        temp = n.copy()  # 원본 수식의 복사본 생성
        for a, b in combo:  # 각 조합에서 괄호 쌍을 찾아
            temp[a] = temp[b] = ""  # 해당 괄호를 제거.
        answer.append("".join(temp))  # 괄호가 제거된 식을 answer 배열에 추가.

# 중복 제거 및 정렬
answer = sorted(set(answer))  # 중복을 제거하고 사전 순으로 정렬.
print("\n".join(answer))  # 결과를 각각 별도의 줄에 출력.

 

combination을 몰라서 조금 헤맸다. 슬슬 어려워지네 문제들이..