[Algorithm] programmers/kakao/찾프마/사칙연산

문제 설명

사칙연산에서 더하기(+)는 결합법칙이 성립하지만, 빼기(-)는 결합법칙이 성립하지 않습니다.
예를 들어 식 1 - 5 - 3은 연산 순서에 따라 다음과 같이 다른 결과를 가집니다.

((1 - 5) - 3) = -7
(1 - (5 - 3)) = -1
위 예시와 같이 뺄셈은 연산 순서에 따라 그 결과가 바뀔 수 있습니다.
또 다른 예로 식 1 - 3 + 5 - 8은 연산 순서에 따라 다음과 같이 5가지 결과가 나옵니다.

(((1 - 3) + 5) - 8) = -5
((1 - (3 + 5)) - 8) = -15
(1 - ((3 + 5) - 8)) = 1
(1 - (3 + (5 - 8))) = 1
((1 - 3) + (5 - 8)) = -5
위와 같이 서로 다른 연산 순서의 계산 결과는 [-15, -5, -5, 1, 1]이 되며, 이중 최댓값은 1입니다.
문자열 형태의 숫자와, 더하기 기호(+), 뺄셈 기호(-)가 들어있는 배열 arr가 매개변수로 주어질 때, 서로 다른 연산순서의 계산 결과 중 최댓값을 return 하도록 solution 함수를 완성해 주세요.

제한 사항

arr는 두 연산자 +, - 와 숫자가 들어있는 배열이며, 길이는 3 이상 201 이하 입니다.
arr의 길이는 항상 홀수입니다.
arr에 들어있는 숫자의 개수는 2개 이상 101개 이하이며, 연산자의 개수는 (숫자의 개수) -1 입니다.
숫자는 1 이상 1,000 이하의 자연수가 문자열 형태로 들어있습니다.. (ex : 456)
배열의 첫 번째 원소와 마지막 원소는 반드시 숫자이며, 숫자와 연산자가 항상 번갈아가며 들어있습니다.

접근법

>> 역시 from itertools import permutations를 사용한 방식은 효율성 측면에서 너무 효율 낮음
>> permutation을 사용하게 된 계기, 아이디어?
>> 연산자들의 수행 순서의 개수는 연산자 개수가 n일때 n!에 해당한다.
>> 무식하게 다 탐색해보는 것이다. >> 역시 무식한 녀석은 효율성에서 탈락하는구나

코드_효율성 bad

from itertools import permutations
def solution(arr):
    n = len(arr)
    m = n//2
    idx = [2*e+1 for e in range(m)] 
    arr = [e if i%2 else int(e) for i, e in enumerate(arr)]
    permlist = list(permutations(idx))
    answer = []
    for perm in permlist:
        temp = arr[:]
        n = len(perm)
        j = 0
        while j < n:
            idx = perm[j]
            a = temp[idx-1]
            b = temp[idx+1]
            operation = temp[idx]
            if operation == "+":
                temp = temp[:idx-1]+[a+b]+temp[idx+2:]
            else :
                temp = temp[:idx-1]+[a-b]+temp[idx+2:]
            perm = [e-2 if e > idx else e for e in perm]
            j+= 1
        answer.append(temp[0])

    print(answer)
    return max(answer)


arr =["1", "-", "3", "+", "5", "-", "8"]
result=solution(arr)
print(result)

코드_참고_github.com/wh2per

## 보면서 공부하겠습니다!
def solution(arr):
    d = [[[0 for x in range(2)] for y in range(201)] for z in range(201)]
    oper = []

    # 숫자로 변환
    for i in range(len(arr)):
        if arr[i] == "+":
            oper.append(1001)
        elif arr[i] == "-":
            oper.append(1002)
        else:
            oper.append(int(arr[i]))
            d[i][i][0] = oper[i]
            d[i][i][1] = oper[i]

    for i in range(2,len(arr),2): # 첫 숫자, 연산자 이후로 끝까지 (숫자, 연산자) 세트로 증가   -> 범위의 종료 지점 설정
        for j in range(0,len(arr)-i,2):    # 처음부터 len-i 길이를 전부 검사                   -> 범위의 시작 시점 부터 종료 지점까지 검사
            tmax = 0
            tmin = 0
            max_n = -9999999
            min_n = 9999999
            for k in range(j+1,i+j,2):          # 연산 시작
                if oper[k] == 1001:        # +
                    tmax = d[j][k - 1][0] + d[k + 1][i + j][0]
                    tmin = d[j][k - 1][1] + d[k + 1][i + j][1]
                    if tmax > max_n:
                        max_n = tmax
                    if tmin < min_n:
                        min_n = tmin
                elif oper[k] == 1002:       # -
                    tmax = d[j][k - 1][0] - d[k + 1][i + j][1]
                    tmin = d[j][k - 1][1] - d[k + 1][i + j][0]
                    if tmax > max_n:
                        max_n = tmax
                    if tmin < min_n:
                        min_n = tmin
            d[j][j + i][0] = max_n
            d[j][j + i][1] = min_n
    return d[0][len(arr) - 1][0]