BOJ 2800. 괄호 제거

🔎 BOJ 2800. 괄호 제거 (골드5)

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

2800번: 괄호 제거

 

💡 SOL

import sys
import copy

#1 : 입력
A = list(sys.stdin.readline().strip())
gual = []
stack = []

#2 : stack으로 괄호 쌍 처리 / gual 리스트에 괄호쌍의 인덱스 위치 저장
for i in range(len(A)):
    if A[i] == '(':
        stack.append(i)
    elif A[i] == ')':
        gual.append([stack.pop(), i])

#3 : gaul 리스트의 모든 괄호쌍에 대해 부분집합 생성하여 부분집합 해당 괄호쌍만 제거하고 answer 리스트에 추가
answer = []
for i in range(1, 1<<len(gual)):
    A_copy = copy.deepcopy(A)
    for j in range(len(gual)):
        if i & (1<<j):
            A_copy[gual[j][0]] = ""
            A_copy[gual[j][1]] = ""
    answer.append(''.join(A_copy))

#4 : answer 중복제거 + 사전순 정렬(문제조건) 하여 출력
answer = sorted(list(set(answer)))
for a in answer:
    print(a)

 

 

💭 TIL

비트연산자 부분집합 생성

• 1<<n = 2^n
  • 원소 n개인 집합의 각각 0/1(불포함/포함) 모든 경우의 수
• a & b
  • a와 b의 교집합
  • 예를 들어, a = 101, b = 001일 때 True / a = 101, b = 010 일 때 False
• ex) A = [1, 2, 3] 일 때

n = len(A)

for i in range(1<<n):      # n개 집합의 0/1 모든 경우의 수
    for j in range(n):     # 각 자리수를 나타냄 (n번째 원소)
        if i & (1<<j):
            pass           # 해당 부분집합의 경우에 대한 연산

 

문제 조건 주의 !!

"어떤 식을 여러 쌍의 괄호가 감쌀 수 있다." 

 → 생성된 문자열들 중 중복 있을 수 있으므로 제거해야 함.