[알고리즘] 그리디(Greedy) 백준 1541번 - 잃어버린 괄호

1차 코드

num_list = input().split('-')

result = []
for i in num_list:
  result.append(sum(list(map(int, i.split('+')))))

answer = 0
for i in range(len(result)):
  if i == 0:
    answer += result[i]
  else:
    answer -= result[i]

print(answer)

10 + 20 - 30 + 40 + 50 - 60 + 70 이 주어졌다고 가정해보자.
(10+20) - (30+40+50) - (60+70) 과 같이 - 를 기준으로 괄호를 묶고, 맨 앞 연산을 제외하고 모두 빼주면 가장 작은 값이 나온다.

1. result 배열을 만들고 ( ) 안에 있는 숫자를 각각 더해주었다.
2. 이후, 첫 번째 요소만 더한 후, 나머지를 모두 빼주면 답이 나온다.

2차 코드

num_list = input().split('-')

result = 0
for i in num_list[0].split('+'):
  result += int(i)

for i in num_list[1:]:
  for j in i.split('+'):
    result -= int(j)

print(result)

다른 코드를 참고하며 굳이 result 배열을 만들 필요가 없다는 것을 알게 되었다. for 문을 돌려가며, 그대로 더하고 빼주면 된다.