[백준] #2800 - 괄호 제거

2023/7/11

골드5

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

2800번: 괄호 제거

 

 

🔎 분석

굉장히 흔해 보이는 문제이고, 풀어봤겠지라고 생각했던 문제.

근데 막상 풀려고 하니까 어떻게 해야할지 모르겠어서 많이 고민했다.

 

✏️ 과정

1.

( 여는 괄호가 나오면 stack에 index를 저장해두고,

) 닫는 괄호가 나오면 그때 stack을 pop해서 가장 근처의 여는 괄호 index를 꺼내고 두 index를 묶어서 다시 배열에 저장한다.

2.

그러면 괄호 쌍으로 된 배열이 생기게 되는데 그 배열에서 조합을 통해 가능한 모든 조합을 찾는다 (괄호 쌍 배열의 크기가 4라면 4, 3, 2, 1 전부 다 구하기)

3.

모든 조합에 따라 () 괄호 쌍 제거하기

→ 제거하는 방식도 고민을 많이 했는데, python에서는 string의 각 요소를 수정할 수 없기 때문에 입력받은 식을 list로 변환해서 괄호를 제거한 후, 다시 string으로 되돌려서 출력하도록 하였다.

4.

사전식으로 출력하기 위해 sorted를 사용하였다.

 

📍TIP

이때, 중복을 구하고 괄호를 제거하는 과정에서 중복을 제거했다고 생각하고 이대로 제출했는데 틀렸습니다가 나왔다. 예제가 다 돌아가서 왜 안되는지 고민했는데, 중복 제거가 문제였다. 그래서 출력할 때 다시 한 번 중복을 피하도록 하여 해결했다.

 

💻 코드

from itertools import combinations

in_ = input()

st_1 = []
list_ = []

for idx, ex in enumerate(in_):
    if ex == '(':
        st_1.append(idx)
    elif ex == ')':
        list_.append([st_1.pop(), idx])

res = []
for i in range(len(list_)):
    comb_list = list(combinations(list_, i+1))

    
    for j in range(len(comb_list)):
        tmp_in_ = list(in_)
        for k in range(i+1):
            # string은 요소를 바꿀 수 없으므로 list로 변환     
            tmp_in_[comb_list[j][k][0]] = '_'
            tmp_in_[comb_list[j][k][1]] = '_'
    
            
        # list를 다시 string으로 변환하기 위해 Join 사용
        tmp_in_ = ''.join( s for s in tmp_in_)
        tmp_in_ = tmp_in_.replace('_', '')
        res.append(tmp_in_)
    
prev_result = ''
for result in sorted(res):
    if prev_result != result:
        print(result)
    prev_result = result