BOJ - 괄호 제거 2800번 (python)

❓ 문제 - 백준 괄호 제거 2800번 - python 풀이법

출처 

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

2800번: 괄호 제거

 

 

📝 문제해결법

1. 이 문제의 핵심은 스택과 조합 이용이다.

• input 문자열을 for문을 통해 하나씩 보면서 만약 '(' 이면 해당 자리의 인덱스를 Stack에 append
• 문자열 중 ')'이면 Stack에서 pop하여 '('의 인덱스 값을 얻고, ')'의 인덱스 값과 함께 list에 같이 인덱스 값을 append
• 1 ~ 괄호 쌍의 갯수만큼 지울 괄호의 조합을 만들어서 지울 괄호쌍의 인덱스들을 cut에 append
• 문자열을 하나씩 돌면서 지울 괄호쌍의 인덱스를 빼고 나머지 문자열을 result에 append 해주고 result의 문자열을 answer에 append

2. 두 번째 핵심은 중복 제거와 사전 순으로 출력하는 것이다.

• '(((1)))(2)' 을 하면 중복된 문자열이 생성되므로 마지막에 차집합을 이용해서 괄호가 제거된 문자열의 중복을 제거
• 출력에 사전 순으로 출력하기 위하여 정렬(sorted)

 

 

💻 소스코드

from itertools import combinations

data = input()


stack = []
array = []
answer = []
for i in range(len(data)):
    if data[i] == '(':
        stack.append(i)
    elif data[i] == ')':
        num = stack.pop()
        array.append([i, num])

for i in range(1, len(array)+1):
    for com in list(combinations(array, i)):
        cut = []
        result = []
        for c in com:
            x, y = c
            cut.append(x)
            cut.append(y)
        for d in range(len(data)):
            if d in cut:
                continue
            else:
                result.append(data[d])
        answer.append(''.join(result))

answer = set(answer)
answer = list(answer)
for a in sorted(answer):
    print(a)

 

🧐 Ellen's Thinking

처음 스택 접근은 생각났지만 조합을 바로 이용해야겠다고 생각하지 못 했다. 이런 문제들을 많이 접근하여서 기본기를 탄탄하게 쌓아야겠다. 그리고 중복 부분을 예측하지 못해 자꾸 boj에서 틀렸다고 판정을 받았고 질문 게시판에서 중복이라는 핵심도 존재한다는 것을 알 수 있었다.