[Python] 백준 2800 - 괄호 제거 문제 풀이

Overview

BOJ 2800번 괄호 제거 Python 문제 풀이
분류: Data Structure (자료구조)

---

문제 페이지

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

---

풀이 코드 1 - DFS

from sys import stdin


res = set()


def dfs(orig, brackets, removes, cur):
    if cur == len(brackets):
        if not removes:
            return
        temp = ''
        for i, char in enumerate(orig):
            if i not in removes:
                temp += char
        res.add(temp)
        return

    dfs(orig, brackets, removes, cur + 1)
    dfs(orig, brackets, removes + brackets[cur], cur + 1)


def main():
    x = stdin.readline().rstrip()
    stack = []
    brackets = []

    for i, char in enumerate(x):
        if char == '(':
            stack.append(i)
        elif char == ')':
            brackets.append([stack.pop(), i])

    dfs(x, brackets, [], 0)
    print(*sorted(list(res)), sep='\n')


if __name__ == "__main__":
    main()

dfs 탐색을 통해 각 단계에서 현재 괄호를 지운 식과 안 지운 식을 생성한다.

---

풀이 코드 2 - itertools 이용

from sys import stdin
from itertools import combinations


def main():
    x = list(stdin.readline().rstrip())
    stack, brackets = [], []

    for i, char in enumerate(x):
        if char == '(':
            stack.append(i)
        elif char == ')':
            brackets.append([stack.pop(), i])

    res = set()
    for i in range(1, len(brackets) + 1):
        for comb in combinations(brackets, i):
            new = x[:]
            for o, c in comb:
                new[o], new[c] = '', ''
            res.add(''.join(new))

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


if __name__ == "__main__":
    main()
    

itertools의 combinations 기능을 이용하여 제거 괄호 개수 별로 조합들을 생성하고, 식을 만든다.