[백준] 2800 : 괄호 제거 (Python)

 

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

 

---

 

아이디어

해당 문제에서 구하자고자 하는 인사이트는 다음과 같다.

'특정 괄호 쌍을 제거하는 모든 경우의 수를 구한다.'

브루트포스의 문제이므로, 괄호 제거에 대한 모든 경우의 수를 파악하기 전에 올바른 괄호 쌍이 어떻게 되는지 먼저 파악해야 한다. 다시 말해, 올바른 괄호 쌍의 인덱스 튜플을 알기만 하면, 괄호 제거의 경우들을 파악할 수 있다.

그렇다면, 어떻게 올바른 괄호 쌍들의 인덱스를 저장할 수 있을까? Stack을 이용하면 쉽게 해결 가능하다. 왼쪽 괄호( '(' )를 스택에 삽입하고, 오른쪽 괄호( ')')를 조회 시 스택에서 pop을 하여 저장하면 된다.

이해를 돕기 위해 다음의 예제를 확인하길 바란다.

예제 이해 : 올바른 쌍들의 인덱스를 저장하는 tmp배열을 구하는 과정

 

이렇게, 올바른 쌍들의 인덱스를 저장하는 tmp 배열을 구했다면, 괄호 제거에 관한 경우의 수들을 파악하면 된다. '몇 개의 쌍들 중에서 중복되지 않는 괄호들을 제거'하는 것이므로, 조합(combination)임을 알 수 있다.

이해를 돕기 위해 다음과 같은 예제로 answer의 개수를 파악해보았다.

 

이를 통해 코드를 구현하면 되는데 이 때 주의점이 존재한다. '서로 다른 식'과 '사전 순' 출력이다. 이를 처리하기 위해 다음 사항을 인지하면 된다.

• 특정 괄호 제거를 통해 얻은 다양한 식들을 answer라는 배열에 저장시킬 때, 같은 식이 존재하는지 여부를 체크하여 저장에 유의한다.
• answer 배열을 정렬하여, 사전 순으로 출력한다.

 

정답 코드

# https://www.acmicpc.net/problem/2800
# 괄호제거
# 문자열, 스택, 브루트포스

input=__import__('sys').stdin.readline
from itertools import combinations

S=input()[:-1]

## 올바른 괄호쌍 인덱스 검색 및 저장
bracket_idxs,stk=[],[]
for i in range(len(S)):
    if S[i]=='(':
        stk.append(i)
    elif S[i]==')':
        bracket_idxs.append((stk.pop(),i))

## 괄호 제거 경우들 찾기
answer=set() # 서로 다른 식 중복 제거를 위함
for num in range(1,len(bracket_idxs)+1):
    for i in combinations(bracket_idxs,num):
        tmp=[*S]
        for left,right in i:
            tmp[left]=''
            tmp[right]=''
        answer.add(''.join(tmp))

for i in sorted(answer): # 사전순
    print(i)