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

프로그래머스 사칙연산 배정 문제 보기

풀이

oper : operator 리스트
nums : operand 리스트
find(s,e,case) : oper의 인덱스를 기준으로 s부터 e까지 연산자를 사용했을때 만들수 있는 max(case='max'), min(case='min')값 리턴

operator를 기준으로 dp를 사용했다.
구간의 최대, 최소값을 모두 저장해야 하므로 max_dp, min_dp 2개를 사용.

구간의 최대, 최소값을 구할때 주의할점
oper[i]가 '+'일때

max = s~i까지의 max + i+1~e까지의 max   
min = s~i까지의 min + i+1~e까지의 min  

oper\[i\]가 '-'일때  
max = s~i까지의 max - i+1~e까지의 min  
min = s~i까지의 min - i+1~e까지의 max  

Code

def solution(arr):
    oper = []
    nums = []
    for i,c in enumerate(arr):
        if i%2 == 0: nums.append(int(c))
        else: oper.append(c)

    max_dp = {}
    min_dp = {}
    def find(s,e,case):
        if s>e: return nums[s]
        if case == 'max':
            max_v = max_dp.get((s,e))
            if max_v != None: return max_v
        if case == 'min':
            min_v = min_dp.get((s,e))
            if min_v != None: return min_v

        maxi = -999999999
        mini = 999999999

        for i in range(s,e+1):
            if oper[i]=='+':
                new_max = find(s,i-1,'max') + find(i+1,e,'max')
                new_min = find(s,i-1,'min') + find(i+1,e,'min')
            else:
                new_max = find(s,i-1,'max') - find(i+1,e,'min')
                new_min = find(s,i-1,'min') - find(i+1,e,'max')
            if new_max > maxi:
                maxi = new_max
            if new_min < mini:
                mini = new_min

        max_dp[(s,e)] = maxi
        min_dp[(s,e)] = mini

        if case == 'max': return maxi
        else: return mini

    end = (len(arr)-1)//2
    answer = find(0,end-1,'max')
    return answer