[알고리즘/자료구조] 2800번 : 괄호제거 - python

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

2800번: 괄호 제거

---

• 문제
• 소요시간: 

---

• 설계하기(접근방법) 

1. 문자열을 입력받는다

2. 알고리즘 해석

괄호의 개수가 n개인 경우

나올 수 있는 식의 개수는 2^n 개이다

원래의 식을 제외하면 2^n-1개의 식을 출력해야 한다.

 

1) stack을 통해 각각의 괄호의 쌍을 구한다

1 : '('가 입력되면 스택에 index를 append한다

2: ')'가 입력되면 스택 맨위 에 있는 index를 팝하고, 자신의 인덱스와 쌍을 이루어 리스트의 형태로 다른 곳에 append한다

 

2) 만들어진 괄호의 쌍 수만큼 binary 리스트를 생성한다

ex) ['00','01',10','11] -> ['00','01','10']

 

이 이진 리스트를 순회하며

00인 경우 -> 첫번째 괄호 쌍 두 번째 괄호쌍 모두 제거

01 인 경우 ->첫번째 괄호 쌍 제거 두 번째 괄호쌍 유지

....

해서 각 결과를 ans_list에 append한다

ans_list에 중복된 결과를 set()을 통해 제거해준 후

다시 리스트로 돌린 후 사전순으로 sort 한다

 

3. 결과를 사전 순으로 출력한다.

 

 

---

• 코드(출력)

n = input()
temp = n
stack = []
bracket = []
bin_list = []
ans = []


def bin_num(x):
    return x[2:]


for i in range(len(n)):
    if n[i] == '(':
        stack.append(i)
    if n[i] == ')':
        bracket.append([stack.pop(), i])

for i in range(2**len(bracket)):
    bin_list.append(bin_num(bin(i)).zfill(len(bracket)))

bin_list.pop()

for i in range(2**len(bracket) - 1):  # 0 ~ 7
    for j in range(len(bracket)):  # 0 ~ 2
        if bin_list[i][j] == '0':
            n = list(n)
            n[bracket[j][0]] = 'F'
            n[bracket[j][1]] = 'F'
    ans.append(n)
    n = temp

remove_set = {'F'}

for i in range(len(ans)):
    ans[i] = [j for j in ans[i] if j not in remove_set]


for i in range(len(ans)):
    ans[i] = ''.join(ans[i])

ans = set(ans)
ans = list(ans)
ans.sort()

for i in ans:
    print(i)

 

---

• 얻어갈 부분

1. 정수를 이진법으로 바꾸는 방법을 알았다

2. 이진법의 앞 부분 두개를 제거한 후 zfill()을 사용하면 0001 0010 와 같은 형태를 얻을 수 있다

3. 리스트에서 원하는 원소 ex)'F'를 모두 제거하는 방법을 알게 되었다.

-> remove_set ={'F'}를 선언 한 후

ans[i] = [j for j in ans[i] if j not in remove_set]

ans[i] = ans[i] 내의 원소를 순회하는데, remove_set 내에 없는 원소들로 초기화된다