백준 2800 : 괄호 제거

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

2800번: 괄호 제거

 

해결 방법 : stack, combinations

• 서로 pair가 되는 괄호쌍에 대한 index를 먼저 추출한다.
  • '('를 stack.push 하다가,  ')'가 나올때 stack.pop 하면 두 괄호가 쌍이다.
• 모든 괄호쌍들의 중복 없는 부분집합에 따라 괄호 제거를 하면 된다.
  • combinations(brace_list, 1~len(brace_list))로 모든 부분집합을 구할 수 있다.
  • 기존 수식에서 각 부분집합에 포함된 인덱스 위치를 제거.
    • 인덱스 내림차순 정렬한 뒤 제거하면 인덱스가 꼬이지 않는다. 
• ((1)) + 1 과 같은 테스트 케이스가 존재하는 것 같다 → 마지막에 중복 제거 필요!

import sys
input = sys.stdin.readline
from itertools import combinations

def solution(ex):
    answer, stack, braces = [], [], []

    for i, e in enumerate(ex):
        if e == '(':
            stack.append(i)
        elif e == ')':
            braces.append((stack.pop(), i)) # 괄호 쌍 저장

    for i in range(len(braces)):
        for comb in combinations(braces, i+1): # 모든 부분집합 탐색
            cur_case = sorted([e for each in comb for e in each], reverse=True) # 순수 인덱스 추출, 내림차순 정렬
            temp = list(ex) # 인덱스로 요소 제거를 위해 리스트로 변환

            for e in cur_case: # 괄호 제거
                del temp[e]

            answer.append(''.join(temp))

    return '\n'.join(sorted(list(set(answer)))) # 중복제거

if __name__ == '__main__':
    ex = input().strip()
    result = solution(ex)
    print(result)

참고로 인덱스만 추출하는 [e for each in comb for e in each] 대신 itertools.chain.from_iterable(comb)도 가능하다.