알고리즘 짤 때 가장 한심스러운 순간 (1541번 잃어버린 괄호)

#1541번 잃어버린 괄호 https://www.acmicpc.net/problem/1541

1541번: 잃어버린 괄호

모든 경우의 수를 구해야겠다는 판단에 BFS 그래프탐색으로 진행했다. 

 

틀린코드

from collections import deque
import sys
# 데이터 변환
t = input()
data = []
prev = 0
for i in range(len(t)):
    if t[i] in ["+", "-"]:
        data.append(str(int(t[prev:i])))
        data.append(t[i])
        prev = i+1
data.append(str(int(t[prev:])))
# 0-2, 2-4, 4-6 -> 홀수 인덱스는 부호가 존재하기 때문이다.
que = deque()
que.append(data)
answer = sys.maxsize
while que:
    d = que.popleft()
    if len(d) == 1:
        answer = min(answer, int(d[0]))
    else:
        for i in range(0, len(d)-2, 2):
            sub_data = d[:i] + [str(eval("".join(d[i:i+3])))] + d[i+3:]
            que.append(sub_data)
print(answer)

완벽하다고 판단했는데 메모리 초과가 났다.

하지만 아무리 생각해봐도 메모리를 줄일 수 있는 요소는 보이지 않았다.

 

고민 끝에 결국 검색하기로 결정했다.

 

정답은... 그냥 연산이다.

알고리즘 따위 필요없다. 단순 판단이다.

수의 합이 최솟값이 나와야 하기 때문에 +연산을 우선한 뒤 - 연산을 진행하면 된다.

아이고....... 고민한 시간들이 허탈하게 느껴졌다.

 

아무튼 풀이방법은 다음과 같다.

1. -연산이 마지막이기 때문에 주어진 수식을 -기준으로 split한다.

2. + 연산자를 포함한 문자열들이 리스트로 바뀐다.

3. 제일 처음 값만 더해준 뒤, 나머지 값들을 전부 연산한 뒤 빼준다.

4. 최솟값 완성

 

정답코드

data = input().split("-")
answer = 0
for i in range(len(data)):
    tmp = data[i].split("+")
    tmp = sum(map(int, tmp))
    if i == 0:
        answer += tmp
    else:
        answer -= tmp
print(answer)

 

 

최근 그래프 탐색에 빠져있던 터라 모든 문제를 그래프로 풀려는 경향이 보인다.

저번 분할 정복 문제 중 Z탐색에서도 그러했듯 무작정 관련 알고리즘을 적용하려 하기보다는 조금은 더 최적의 상황을 고려했으면 좋겠다.