[백준 1541 파이썬] 잃어버린 괄호 (실버2, 그리디)

알고리즘 유형 : 그리디
풀이 참고 없이 스스로 풀었나요? : △ (통과했지만 풀이 참고 후 최적화)

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

소스 코드(파이썬)

expr = input().split("-")
result = sum(map(int, expr[0].split("+")))

for i in range(1, len(expr)):
    i_arr = sum(map(int, expr[i].split("+")))
    result -= i_arr

print(result)

풀이 요약

1. 목표는 식의 값을 최소로 만드는 것이다. 즉 빼는 수를 가장 크게끔 만들면 된다고 예측해볼 수 있다.

2. 마이너스 부호를 기준으로, 그 뒤 플러스 부호를 포함한 모든 수를 괄호로 묶어주면 된다. 분배 법칙&결합 법칙에 의해 양수였던 수들은 모두 음수가 되게 된다. 이 때 만약 마이너스 부호가 하나만 있다면 그 뒤의 모든 양수를 다 괄호로 묶어줘서 음수로 만들어주면 되고, 마이너스 부호가 아예 없다면 괄호 상관없이 그냥 다 더한게 답이다.

3. "-" 문자를 기준으로 split 해주고, 마이너스 부호가 등장하기 이전의 모든 수("-" 없는 경우 전체 모든 수)에 대해, "+" 문자 기준 split 해주고 각 수를 다 더한 값을 result 변수에 할당해준다.

4. 그 뒤부터 for를 돌면서, 각 요소에 대해 "+" 문자를 기준으로 split 해서 수를 다 더하고, 그 값을 result에 빼주면 된다. 이 때 0009같은 0으로 시작하는 수의 경우 int 형변환에서 9로 바뀌니 걱정말자.

배운 점, 부족했던 점

• 처음 작성한 코드가, 통과는 했지만 되게 비효율적이고 복잡하게 코드를 짜버렸다.
  

  1. "-"로 분할하지 않고, "+", "-"로 모든 수를 분할했다.

  2. 플러스 마이너스 부호 중에 마이너스가 처음으로 등장하는 순서 값을 찾는다.(count에 할당)

  3. 00009 같은 수를 9로 변환하기 위한 for문을 작성했다.

  4. count 이전 인덱스까지 수를 더하고, 그 이후 수는 모두 빼주어서 답을 구했다.(마이너스 부호가 처음 등장한 시점을 기준으로 그 뒤에 모든 수를 다 빼줘버리면 되는 원리이기에)

  이 후 다른 사람의 풀이를 참고하고, 위 코드와 같이 최적화했다.