[프로그래머스] 사칙연산

문제

• 숫자와 덧셈 또는 뺄셈 연산이 주어질 때, 서로 다른 연산순서의 계산 결과 중 최댓값을 리턴하기
  • 3 <= 총 연산 길이 <= 201

 

풀이

• 연산 별 순서를 매겨 전체 경우의 수를 확인하면, 연산 개수는 최대 100개 이므로 $100!$ 이 된다. 불가능!
• 그런데 덧셈은 결합법칙이 성립하기 때문에 뺄셈의 경우에만 추가적인 고려를 하면 된다.
• 뺄셈이 전체 결과에 영향을 주는 경우는 다음과 같다.
  
  • 덧셈끼리의 합을 모두 - 부호로 바꾸기
  • 현재값만 - 부호로 사용하기
• 마지막에서부터 역으로 시작해, - 부호가 나올 때마다 최솟값과 최댓값을 업데이트 한다.
  • 최소 : min(-(덧셈끼리의 합 + 최솟값), -덧셈끼리의 합 + 최솟값)
  • 최대 : max(-(덧셈끼리의 합 + 최솟값), -현재값 + (현재값 제외 덧셈끼리의 합) + 최댓값)

 

def solution(arr):
    
    mins, maxs = 0, 0
    summation = 0
    for i in range(len(arr)-1, -1, -1) :
        if arr[i] == '+' :
            continue
        elif arr[i] == '-' :
            tmpmin, tmpmax = mins, maxs
            mins = min(-(summation + tmpmin), -summation + tmpmin)
            num = int(arr[i+1])
            maxs = max(-(summation + tmpmin), -num+(summation - num)+tmpmax )
            summation = 0
        else :
            summation += int(arr[i])
    maxs += summation
    return maxs

 

References

• 프로그래머스 고득점Kit DP
• tiktaek/ 사칙연산