백준 2800번 : 괄호 제거

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

2800번: 괄호 제거

구현하기도 까다롭고 예외처리도 해줘야해서 개인적으로 어려웠던 문제다.

 

괄호가 포함된 수식이 입력으로 주어진다. 이 수식에서 괄호를 제거해서 만들 수 있는 모든 서로 다른 수식을 구하려고한다. 단, 괄호는 반드시 한 쌍 이상을 제거해야하며 자신과 맞는 짝이 아닌 괄호끼리는 제거할 수 없다. 

 

문제를 이해하는데는 큰 어려움이 없었고 처음 생각한 해결 아이디어는 이렇다. 괄호쌍이 3개가 있다고 가정하면,  주어진 수식에서 괄호쌍의 인덱스 정보를 저장해놓고 3개의 괄호쌍을 모두 없애는 경우 또는 2개만 없애는 경우 또는 1개만 없애는 경우로 나누어 괄호를 없앴을 때 수식을 출력한다. (괄호를 없애지 않는 경우는 제외한다.) 결국 3개의 괄호쌍 중에서 경우에 따라 선택한 괄호쌍 조합을 수식에서 제거해주면 된다.

그런데 나는 재귀를 통해 풀 수 있을것 같아서 다른 방식으로 구현했다.

 

입력된 수식에서 0번 인덱스부터 순서대로 닫는 괄호( ')' )가 아닌 문자는 리스트에 저장하고, 닫는 괄호가 나오면 현재 리스트에 저장된 문자들 중 가장 인덱스 번호가 높은 여는 괄호 ( '(' ) 를 찾는다. 이때 찾은 괄호가 지금 검사하는 닫는 괄호와 쌍을 이루는 괄호다. 이제 이 괄호쌍을 제거할 경우와 남길 경우 각각에 대해 리스트를 갱신해준다. 제거한다면 리스트에서 여는 괄호를 pop해주고, 남긴다면 괄호쌍을 다른 문자로 바꿔줘야한다. 그 이유는 이후 호출되는 재귀함수에서 닫는 괄호와 짝을 이루는 여는 괄호를 찾을때, 문자들이 저장된 리스트에 닫는 괄호가 남아있기 때문에 잘못된 쌍을 찾게되기 때문이다. 수식의 마지막 문자까지 검사를 마치면 재귀호출동안 바꿔줬던 괄호 문자를 정상적으로 바꿔준 뒤 사전순으로 정렬하여 출력해준다.

 

여기서 끝인 줄 알았지만 아니다. 수식에서 괄호쌍을 삭제하는 모든 경우를 구했지만, 그 경우가 동일하게 나올 수 있다. 이런 경우는 중복된 케이스를 제거하여 출력해줘야 한다.

import sys
input = sys.stdin.readline

def sol(i, d):

    if i == len(s):
        r.add((''.join(d)).replace('[', '(').replace(']', ')'))
        return

    if s[i] == ')':
        k = len(d)-1
        while d[k] != '(':
            k -= 1

        t1, t2 = d[:], d[:]
        t1[k] = '['
        t1.append(']')

        t2.pop(k)
        sol(i+1, t1)
        sol(i+1, t2)

    else:
        d.append(s[i])
        sol(i+1, d)

r = set()
s = input().rstrip()
sol(0, [])
r = sorted(list(r))
print(*r[1:], sep='\n')