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

문제 설명

수식이 주어졌을 때 쌍이 맞는 올바른 괄호를 제거해야 한다.
이 때 괄호를 제거할 수 있는 모든 경우의 수식을 사전 순으로(lexicographically) 정렬하여 출력하는 문제이다.

참고로 괄호는 사전 순으로 숫자보다 앞이다.

(0/(0))이라는 수식이 주어졌다면

(0/0)
0/(0)
0/0

코드 구현

문제를 처음 봤을 때 스택을 이용해서 괄호를 제거해야겠다는 생각이 들었다.
그러나 여러 경우의 수의 괄호를 제거해야 하므로 그 부분이 어렵게 느껴졌다.

가장 먼저 생각한 것은 제거할 수 있는 괄호의 인덱스 쌍들을 스택을 이용해 구한 다음 저장해두고 powerset을 구하는 것이었다. 그러나 아쉽게도 powerset을 구현해놓은 라이브러리는 없었다.

대신 itertools를 활용해 조합을 구할 수 있었기 때문에 반복문과 combination을 활용하여 인덱스 쌍의 powerset을 구할 수 있었다.

스택과 조합 이용

import itertools
 
exp = list(input())

stack, tuples = [], []

results = set()

for i, e in enumerate(exp):
    if e == "(":
        stack.append(i)
    elif e == ")":
        tuples.append((stack.pop(), i))

for n in range(1, len(tuples) + 1):
    for ts in itertools.combinations(tuples, n):
        result = exp[:]
        for i, j in ts:
            result[i] = ""
            result[j] = ""
        results.add("".join(result))

for r in sorted(results):
    print(r)

아이디어에 맞춰서 results를 list로 사용해서 코드를 짜봤다. 그러나 결과는 틀렸었다.

결과 중에 중복되는 것이 있었기 때문이었다. 분명 조합을 사용하여 제거하는 괄호가 중복되는 일은 없을텐데 어째서 틀리는 것인지 이해가 되지 않았다.

알고보니 예를 들어 ((0))/0 같은 경우에는 (0, 4) 괄호를 제거해도 (0)/0이고 (1, 3) 괄호를 제거해도 (0)/0이기 때문에 중복된 결과가 나오는 것이었다.

그래서 results를 set으로 만들어 중복된 결과가 나오는 것을 피했다.