오늘의 문제
https://www.acmicpc.net/problem/1541
간단한 문젠데 잘못 이해해서 시간이 오래걸려버린 문제였다.
포인트 쳌쳌
괄호의 개수는 여러 개가 될 수 있다 처음에 괄호를 딱 한쌍만 쳐야 한다고 생각한 것이 문제였다.
이것 또한 그리디스럽게 생각해보자.
- 괄호는 어디에나 들어갈 수 있고, 숫자의 위치는 변하지 않으며, 연산은 +와 -만 존재한다.
- 결과값이 최소가 되려면 작은수에서 큰 수를 빼야 한다.
- 그렇다면 뺄셈과 그 다음 뺄셈 사이의 + 연산을 모두 수행하고 그 값들을 첫 숫자에서 하나씩 빼준다면?
다음의 수식이 있다고 가정해본다.
10 - 2 + 2 - 1 - 5 - 1 + 1 + 1 + 1
최솟값을 도출하기 위해선느 작은수에서 큰 수를 빼야하고, 빼기 위해서 모든 뺄셈 뒤에 괄호를 친다.
10 - (2 + 2) - (1) - (5) - (1 + 1 + 1 + 1) 이렇게 칠 수 있을 것이다.
그리고나서 괄호 안에 있는 덧셈들을 먼저 수행 하고 피연산자들을 list로 구성한다.
new = [10, 4, 1, 5, 4] 이들을 순서대로 가장 앞쪽 원소인 10에서 하나씩 빼준다. 그러면 연산 완료!
위 가정을 코드로 나타낸 것이 다음의 풀이 코드이다. 문자열 파싱만 잘 생각해보면 어렵지 않은 문제일 것이다!
처음에 문자열을 숫자, ‘-‘, ‘+’문자 따로따로 조각내고 붙이고 하는 것에만 신경을 썼더니 문제 풀이에 도움이 되지 않았다,,,,,
풀이 코드
r = input().split('-')
number = []
new_list = []
#sum_ = 0
#print(r)
for i in range(len(r)):
if '+' in r[i]:
#+로 연결된 수식(문자열)인 경우
a = list(map(int, r[i].split('+')))
new_list.append(sum(a))
else:
#숫자인 경우
new_list.append(int(r[i]))
result = new_list[0]
for i in range(1, len(new_list)):
result -= new_list[i]
print(result)