[백준] 2800번 - 괄호 제거

chanyeong kim·2022년 7월 16일
0
post-thumbnail

📩 출처

문제

어떤 수식이 주어졌을 때, 괄호를 제거해서 나올 수 있는 서로 다른 식의 개수를 계산하는 프로그램을 작성하시오.

이 수식은 괄호가 올바르게 쳐져 있다. 예를 들면, 1+2, (3+4), (3+4*(5+6))와 같은 식은 괄호가 서로 쌍이 맞으므로 올바른 식이다.

하지만, 1+(23, ((2+3)4 와 같은 식은 쌍이 맞지 않는 괄호가 있으므로 올바른 식이 아니다.

괄호를 제거할 때는, 항상 쌍이 되는 괄호끼리 제거해야 한다.

예를들어 (2+(22)+2)에서 괄호를 제거하면, (2+22+2), 2+(22)+2, 2+22+2를 만들 수 있다. 하지만, (2+22)+2와 2+(22+2)는 만들 수 없다. 그 이유는 쌍이 되지 않는 괄호를 제거했기 때문이다.

어떤 식을 여러 쌍의 괄호가 감쌀 수 있다.

입력

첫째 줄에 음이 아닌 정수로 이루어진 수식이 주어진다. 이 수식은 괄호가 올바르게 쳐져있다. 숫자, '+', '*', '-', '/', '(', ')'로만 이루어져 있다. 수식의 길이는 최대 200이고, 괄호 쌍은 적어도 1개, 많아야 10개이다.

출력

올바른 괄호 쌍을 제거해서 나올 수 있는 서로 다른 식을 사전 순으로 출력한다.

👉 생각

  • 스택을 통해 ( 인덱스를 저장하고 ) 가 들어올 때부터 한쌍의 괄호의 인덱스를 리스트로 묶어 다시 다른 리스트 idx의 값으로 넣어준다.
  • idx의 요소들을 가지고 조합을 돌리고 인덱스에 해당하는 괄호 쌍들을 지워서 문자열로 만들고 result에 append 한다.
  • result에 중복값이 존재할 수 있기 때문에 set으로 중복값을 제거하고 정렬한뒤 출력한다.
from itertools import combinations

words = input()
stack = []
idx = []
result=[]
for i in range(len(words)):
    if words[i] == '(':
        stack.append(i)
    elif words[i] == ')':
        idx.append([stack.pop(), i])

for i in range(1, len(idx)+1):
    combs = list(combinations(idx, i))
    for comb in combs:
        check = []
        answer = []
        for com in comb:
            check.append(com[0]); check.append(com[1])

        for j in range(len(words)):
            if j in check:
                continue
            else:
                answer.append(words[j])
        result.append(''.join(answer))
result = set(result)
result = sorted(list(result))
for res in result:
    print(res)

0개의 댓글