[백준 2800 🥇] 괄호 제거

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

2800번: 괄호 제거

문제

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

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

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

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

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

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

입력

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

출력

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

 

 

문제 풀이

• 먼저 stack을 이용해서 여는 괄호 '('를 만나면 stack에 해당 인덱스를 append하고, 닫는 괄호 ')'를 만나면 맨 위에 있는(즉, 가장 최근에 열린 괄호) 괄호의 인덱스를 pop해서 닫는 괄호으 인덱스와 함께 bracket 배열에 저장했다.
• 이 과정을 통해서 올바른 괄호 쌍의 인덱스를 구할 수 있다.
• 이렇게 구한 올바른 괄호 쌍을 각각에 대해서 삭제하는 경우와 삭제하지 않는 경우를 백트래킹을 이용해서 탐색했다.
• backtrackging_eggs 함수를 이용해서 현재 삭제할 괄호의 번호 n과 이미 삭제한 괄호의 개수 cnt를 매개변수로 담아 재귀적으로 탐색한다.
  • 삭제할 괄호의 번호가 위에서 구한 올바른 괄호 쌍의 개수와 같다면 모든 괄호를 탐색한 것이므로 이때 삭제한 괄호의 개수 cnt가 0보다 크다면 괄호의 삭제 여부를 저장한 arr_visited 배열을 돌면서 괄호를 삭제한 문자열을 answer set에 추가한다.
    • 탐색 과정에서 중복되는 문자열이 존재할 수 있으므로 중복 제거를 위해 set 자료형을 사용했다.
  • 아직 올바른 괄호 쌍을 모두 탐색한 경우가 아니라면 다음 두 가지 경우에 대해서 탐색한다.
    • n번 괄호를 삭제하지 않고 다음 괄호로 넘어가는 경우
      •  cnt를 추가하지 않고 바로 다음 괄호의 인덱스를 매개변수 n으로 넘긴다.
    • n번 괄호를 삭제하는 경우
      • bracket[n][0], bracket[n][1] 번 인덱스를 arr_visited 배열에서 False로 표시한다.
      • cnt를 추가하고 다음 괄호를 탐색한다.
      • 다음 괄호 탐색이 끝나면 False로 표시해뒀던 괄호의 인덱스들을 다시 True로 원상복구한다.
  • 위 과정을 거쳐서 answer set을 list로 변환하고 sorted 함수로 사전순 정렬해서 출력한다.

import sys

arr=list(sys.stdin.readline().strip())
answer=set()

bracket=[]
stack=[]
# 괄호 쌍 구하기
for idx in range(len(arr)):
    if arr[idx]=='(':
        stack.append(idx)
    elif arr[idx]==')':
        open=stack.pop()
        bracket.append((open, idx))

visited=[False]*len(bracket)
arr_visited=[True]*len(arr)

# 백트래킹을 사용하자
# n은 현재 삭제할 괄호 번호
# cnt는 삭제된 괄호의 개수
def backtracking(n,cnt):
    # 삭제된 괄호의 개수가 0개 이상이라면 answer에 답 추가
    if n==len(bracket):
        if cnt>0:
            # arr_visited를 이용한 답 추가
            tmp = ''
            for i in range(len(arr_visited)):
                if arr_visited[i]:
                    tmp += arr[i]
            answer.add(tmp)
        return

    # 해당 괄호 삭제 안하는 경우
    backtracking(n+1, cnt)
    # 해당 괄호 삭제 하는 경우
    arr_visited[bracket[n][0]]=False
    arr_visited[bracket[n][1]]=False
    backtracking(n+1, cnt+1)
    arr_visited[bracket[n][0]]=True
    arr_visited[bracket[n][1]]=True


backtracking(0,0)

print(*sorted(list(answer)), sep='\n')