문제 설명
이번 포스팅은 백준 2800번: 괄호 제거 문제에 대한 기록입니다.
문제를 간단히 요약해보면, "괄호가 포함된 수식이 주어지면, 괄호를 제거하여 나올 수 있는 모든 경우의 수의 수식을 출력하는 문제" 입니다.
이 문제에서 한 가지 주의할 점은, 괄호를 제거할 때 서로 쌍을 이루는 괄호끼리 제거해야 한다는 것입니다.
풀이
쌍이 되는 괄호 찾기
서로 쌍이 되는 괄호끼리만 제거하려면, Stack을 이용하여 쌍이 되는 괄호를 찾아 제거할 수 있습니다.
for i in range(len(expr)): #expr: 입력으로 주어진 식
if expr[i] == '(':
stk.append(i)
elif expr[i] == ')':
#indices: 쌍을 이루는 괄호의 index 쌍을 모은 리스트
indices.append((stk.pop(), i)) 입력으로 주어진 식을 for문으로 탐색하며, '('가 나오면 해당 index를 stack에 push합니다.
이후 ')'가 나오면 stack에서 하나씩 pop하면, pop된 index와 현재 탐색 중인 ')'의 index가 서로 쌍을 이루는 괄호의 index가 됩니다. 이렇게 쌍을 이루는 괄호를 서로 tuple로 묶어 한 리스트 indices에 모읍니다.
Combinations를 이용하여 가능한 경우의 수들을 찾기
python에서 제공하는 itertools 모듈의 Combinations를 사용하면 원하는 조합을 보다 쉽게 얻을 수 있습니다.
for i in range(len(indices)):
for comb in combinations(indices, i+1):
temp = expr[:]
for idx in comb:
temp[idx[0]] = temp[idx[1]] = ""
answers.add("".join(temp)) # 중복 제거를 위해 answers는 set을 사용1 ~ indices의 길이만큼 한 번씩 조합을 하면, 괄호를 제거할 수 있는 모든 경우의 수를 모두 조합하게 됩니다.
combinations(조합하고자 하는 요소들이 저장된 리스트, 한 조합의 길이)
위처럼 combinations 함수를 실행하면 원하는 조합들이 저장된 리스트를 반환합니다. 따라서 위 코드에서의 comb 는 여러 조합 중 하나의 경우의 수 조합이 됩니다.
comb 에는 그 경우의 수에 제거하는 괄호 쌍들의 index들이 tuple 형태로 저장되어 있습니다. ex) [(3, 5), (0, 6)]
이제 comb 내의 괄호쌍들을 하나씩 탐색하며 원래 식에서 해당 위치의 괄호를 삭제합니다. (빈 문자 ""를 삽입하여 삭제하는 이유: del이나 remove를 사용하여 실제로 해당 위치의 문자를 삭제하게 되면, 전체 index가 변하여 그 다음 제거에 영향을 주기 때문입니다.)
이렇게 괄호가 삭제된 식을 정답 set에 추가합니다. (set이므로 자동 중복 제거)
이 과정을 모든 개수별 조합, 그리고 해당 개수별 조합 내의 모든 경우의 수마다 반복하면 괄호가 제거된 모든 경우의 수의 식을 얻을 수 있습니다.
for item in sorted(list(answers)):
print(item)최종 정답은 정렬하여 출력해야 하므로 마지막에 정렬하고 출력하는 것 잊지 마세요.
문제 해결!!
결과 코드
from itertools import combinations
expr = list(input())
indices = []
stk = []
answers = set()
for i in range(len(expr)):
if expr[i] == '(':
stk.append(i)
elif expr[i] == ')':
indices.append((stk.pop(), i))
for i in range(len(indices)):
for comb in combinations(indices, i+1):
temp = expr[:]
for idx in comb:
temp[idx[0]] = temp[idx[1]] = ""
answers.add("".join(temp))
for item in sorted(list(answers)):
print(item)