[백준] 2800번 파이썬 - 스택, 조합

문제요약 (2800. 괄호 제거)

 

2800번: 괄호 제거

 

 

풀이를 위한 부연 설명

• 괄호의 위치를 스택을 통해 구현한다
  • 각 괄호의 쌍을 뽑아내야하므로 스택을 사용한다.
• 괄호 쌍을 "포함한다/포함하지 않는다" 이 두 가지 경우에 대한 모든 수를 알아보기 위해 조합을 사용한다.
  • 파이썬 itertools의 combinations를 이용해 경우의 수를 구한다.
  • 여러 가지 같은 경우가 나올 수 있으므로 set()으로 답을 넣는다.
• 조합에 대한 자세한 개념 설명과 연관 문제는 다음 링크를 참고하면 된다.

[코테 알고리즘] 파이썬 기본 / 관련 문제

 

코드 

import sys
input = sys.stdin.readline
from itertools import combinations

exp = list(input().rstrip())

brackets = []

stack = []
for i in range(len(exp)):
    if exp[i] == "(":
        stack.append(i)
    elif exp[i] == ")":
        brackets.append((stack.pop(), i))

answer = set()

for i in range(len(brackets)):
    for comb in list(combinations(brackets, i+1)):
        tmp = exp[:]
        for c in comb:
            tmp[c[0]] = ""
            tmp[c[0]] = ""
        answer.add("".join(tmp))

for item in sorted(list(answer)):
    print(item)

 

 

 

기억할 점

• 모든 조합의 경우의 수를 구하는 반복문을 기억해두면 좋을 것 같다.

for i in range(len(brackets)):
    for comb in list(combinations(brackets, i+1)):
        tmp = exp[:]
        for c in comb:
            tmp[c[0]] = ""
            tmp[c[0]] = ""
        answer.add("".join(tmp))