[백준 1541번] 잃어버린 괄호

expression = input()

# '-'를 기준으로 분할 
# ex) ['00009','00009+00008']
split_exp = expression.split('-')

for i in range(len(split_exp)):
  # 분할된 문자열들을 순서대로 '+'를 기준으로 분할 후 합을 구하기(내부는 +로만 이루어져 있기 때문)
  # 그리고 동시에 앞에 0으로 채워진 문자열들을 정수화 시킨다
  # ex) [9, 17]
  split_plus = list(map(int,split_exp[i].split('+')))
  split_exp[i] = sum(split_plus)

# 첫 번째 원소를 제외한 나머지 원소들은 '-'를 기준으로 파싱되었기 때문에 모두 빼주면 된다.
# ex) 9 - 17
print(split_exp[0] - sum(split_exp[1:]))

이번 문제는 +와 -로 이루어진 계산 식(문자열)을 괄호를 사용해서 최대한 값을 작게 만드는 문제이다.

(문제의 핵심을 찾는 것은 크게 어렵지 않았는데, 문자열에 대한 처리가 조금 까다로웠던 문제였다.)

 

이 문제의 핵심 아이디어는 계산 식의 결과를 최소로 만들기 위해서 뺄셈(-)를 최대한 큰 값으로 해주는 것이다 !

 

따라서 괄호를 사용하여 최대한 많이 빼주기 위해서는 '-'와 '-' 사이의 값들을 전부 하나로 묶어주면 된다.(뺄셈을 기준으로 분할하기 위해 split() 함수 사용)

ex) 45 - 50 + 40 - 20 > 45 - (50+40) - 20

 

이런 식으로 문자열들을 분할한 뒤에, 각 원소들을 계산(eval)해서 연산해주면 되는 줄 알았는데 1가지 조건이 남아있었다.

 

바로 숫자가 0으로 시작할 수 있다는 조건인데, 이를 처리해주기 위해서 map 함수를 사용하여 먼저 정수형으로 변환시킨 후 최종적으로 첫 번째 원소에서 뒤에 위치한 원소들을 모두 빼주었다.(이미 '-'를 기준으로 모두 파싱되었기 때문에 빼주기만 하면 된다.)

 

이번 문제는 현재 상황에서 문제를 해결할 수 있는 방법을 찾는 탐욕적 알고리즘과, 문자열을 처리하는 여러가지 함수를 배울 수 있었던 문제였다 :)