[BOJ] 2800번 - 괄호 제거

 

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

2800번: 괄호 제거

문제

어떤 수식이 주어졌을 때 괄호를 제거해서 나올 수 있는 서로 다른 식을 출력해라.

괄호를 제거할 때 서로 쌍이 되는 것만 제거할 수 있다. 

제거 후, 올바르지 못한 괄호가 생기면 안된다. (올바른 식이 아니다.)

 

풀이

일단 쌍이 되는 괄호의 인덱스를 찾는다.

- 열린 괄호를 만나면 스택에 해당 인덱스를 저장

- 닫힌 괄호를 만나면 스택에서 pop을 한 값과 현재 인덱스를 같이 pair 배열에 저장

이제 괄호 쌍의 수만큼 조합을 구한다. (1, 2, ...)

- 파이썬 내장 itertools를 사용

해당 조합의 요소들 (괄호 쌍 인덱스들)을 보고 해당 부분을 공백으로 바꾼다.

- 조합의 요소들을 다 돌았으면 공백을 제거해준다.

=> 원래는 해당 위치의 괄호를 삭제했는데 그러면 for문이 복잡해진다. 공백으로 바꾸는 게 편하다.

마지막으로 정답 문자열의 중복을 제거하고 출력한다.

 

코드

# 괄호 제거

import sys
from collections import deque
from itertools import combinations
input = sys.stdin.readline()

_str = input.rstrip()

stack = deque()
pair = []
answer = []

# 괄호 쌍 인덱스를 pair에 저장
for i in range(len(_str)):
    if _str[i] == '(':
        stack.append(i)
    elif _str[i] == ')':
        tmp = stack.pop()
        pair.append([tmp, i])

for i in range(len(pair)):
    # pair 수만큼 조합을 생성
    comb = combinations(pair, i+1)

    for data in comb:
        tmp = _str
        for item in data:
            x, y = item
            tmp = list(tmp)
            # 삭제할 괄호를 공백으로 바꿔줌
            tmp[x] = ' '
            tmp[y] = ' '
        answer.append(''.join(tmp).replace(" ", ""))

# 중복 제거 후 정렬
answer = set(answer)
answer = list(answer)
answer.sort()
for ans in answer:
    print(ans)