[Python][백준] 2800번 괄호 제거

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

공부 날짜 : 2023.01.19
정답 참조 여부 : X

괄호가 있는 수식에서 괄호쌍을 없애서 만들 수 있는 수식을 모두 구하는 문제이다.

---

쉬웠다.(파이썬이라서....)

문제 푼 방법은 이렇다
스택을 이용해서 괄호쌍을 서로 찾아줬다.

괄호 쌍은 인덱스만 리스트로 저장해줬고 괄호쌍 중에서 제거 or 유지하는 경우의수 조합을 dfs로 모두 구했다.

그 다음 제거하는 괄호쌍의 인덱스로 문자열에 접근해서 괄호를 제거해줬다.(None처리) None처리된 char을 제외하고 새로 문자열을 만들었고 global에 있는 answer에 넣어준 뒤 sort를 사용해서 첫 제출을 했다.

29%쯤에서 틀렸습니다...

예제 3가지는 모두 정답이었고, 디버깅을 해봐도 내가 의도한대로 완벽하게 수행했다.
예외를 생각하는 힘도 길러야 하긴 하지만, 빨리 풀고싶은 마음에 질문을 찾아봤는데
괄호가 2~3개 중첩인경우 (((a+b))) 어느 괄호를 삭제해도 같은 결과가 나오기 때문에 틀렸다고 나왔다.누가 식을 저 따위로 쓰냐....

처음엔 집합 함수 set이 생각나서 set을 쓰려 했지만 너무 Python함수에 의존하는거 같아서 char을 만든뒤 global answer에 넣을때 answer에 없어야 넣는 조건만 추가해 줬다.

다행히 정답이 나왔지만

파이썬 기능인 sort.... 정렬 알고리즘은 정말 많지만 파이썬으로 알고리즘 문제만 풀어서 그런지 정렬 알고리즘은 정말 약하다. 아마 다른 언어였으면 정렬에서 막혔을거란 생각에 정렬 알고리즘 쪽도 좀 더 공부해야겠다는 생각이 드는 문제였다.

소스코드

import sys
input = sys.stdin.readline
##############################################
# 괄호 쌍 중 제거할 괄호쌍을 고른 조합을 만드는 함수
# 제거할 괄호쌍은 0 유지할 괄호쌍은 1
def Make_combination_dfs(depth = 0, combination = []):
    if depth == len(couple_bracket):
        Make_answer(combination)
        return

    for i in range(2):
        combination.append(i)
        Make_combination_dfs(depth + 1, combination)
        combination.pop(-1)

##############################################
# 제거, 유지가 확정된 조합으로 정답을 만들 함수
def Make_answer(combination):
    # 제거가 없는 조합은 무시
    if 0 not in combination:
        return

    global answer
    string = list(input_data)
    for i in range(len(combination)):
        if combination[i] == 0:
            string[couple_bracket[i][0]] = None
            string[couple_bracket[i][1]] = None

    temp = ""
    for char in string:
        if char != None:
            temp += char
    if temp not in answer:
        answer.append(temp)

##############################################
# 연산 시작

input_data = input().rstrip()

# 괄호 쌍을 찾는 스택
stack = []
# 괄호 쌍을 저장하는 리스트
couple_bracket = []
# 정답을 저장하는 리스트
answer = []

# 데이터를 순회하며 괄호 쌍을 찾음
for index in range(len(input_data)):
    # 괄호가 열리면 stack에 index저장
    if input_data[index] == "(":
        stack.append(index)
    # 괄호가 닫히면 마지막에 열린 괄호(괄호 쌍)의 인덱스와 함께 저장
    elif input_data[index] == ")":
        # 괄호 쌍을 저장한다.
        couple_bracket.append([stack.pop(-1), index])

# dfs실행
Make_combination_dfs()


# 사전 순으로 정렬 (아스키 코드의 숫자를 기준으로)
answer.sort()

for ans in answer:
    print(ans)