[프로그래머스] 수식 최대화

문제 설명

'+', '-', '*'와 숫자들로 이루어진 수식이 string 길이 : [3,100]으로 주어집니다.
'+', '-', '*'의 우선순위를 자유롭게 지정할 수 있을 때, 이 수식을 계산하여서 값이 최대가 될 수 있는 경우를 구하세요!

아이디어

문제에 쓰여 있듯이 연산자 우선순위를 바꿨을 때 3!(=6)가지의 경우가 나온다.
각 경우마다 3개의 연산자에 대해서 순차적으로 연산을 해주면 된다.

이 때 string을 token화했는데
그 이유는 string을 덮어쓰고 하다보면 '302*-200'과 같이 -가 다른 연산자와 같이 나와(의미는 음수값이지만) string에서 '*'기준 operand 숫자를 추출하기가 어렵기 때문이다

갈팡질팡

정말 갈팡질팡을 많이 했던 문제다.... 스택을 활용해서 괄호 연산(우선순위 때문에 이렇게 생각했다)을 해야하나 싶었는데 그냥 토큰화 해서 리니어하게 계산할 수 있겠다고 판단 했다.(왜냐면 어차피 같은 우선순위 연산자면 순서대로 계산을 하기 때문에...)

또 언어 선택에서도 갈팡질팡을 많이 했다..
python의 list가 linked list인줄 알고 pop 연산이 O(1)이겠다 생각을 해서 굳이 파이썬으로 풀었는데...
알고보니 O(n)이었다 ㅎㅎ.. 인턴 문제라 문제 string이 작아서 통과가 된거 같다..

새로 배운거

1. tokenize 할 땐 마지막 토큰을 챙겼는지 확인하자!
2. python의 permutation

from itertools import permutations 
items = ['A', 'B', 'C', 'D'] 
print(list(map(''.join, permutations(items)))) # items의 모든 원소를 가지고 순열을 만든다. 
print(list(map(''.join, permutations(items, 2)))) # 2개의 원소를 가지고 순열을 만든다

3. is 연산자는 char 비교에 사용하지 않는다. ==을 사용하자

코드

from itertools import permutations
def calc_2(left,right,op):
    if op=='+':
        return left+right
    elif op=='-':
        return left-right
    else:
        return left*right


def solution(expression):
    answer = 0
    pr = ['+','-','*']
    pm = list(map(''.join, permutations(pr)))
    print(pm)
    max_candi = 0
    for ctr in range(len(pm)):
        pr = pm[ctr]
        #하나의 테케를 리니어 하게 답을 구한다
        #tokenize
        j= 0
        nums =[]
        ops=[]
        
        for i in range(len(expression)):
            if expression[i] == '+' or expression[i] == '-' or expression[i] == '*':
                num = expression[j:i]
                #print(num,j)
                nums.append(int(num))
                ops.append(expression[i])
                j = i+1
        num = expression[j:len(expression)]
        nums.append(int(num))
        #print(nums, ops)
        
        for opi in range(3):
            op = pr[opi]
            #print("op = ",op)
            i=0
            while i<len(ops):
                if ops[i] == op:
                    res= calc_2(nums[i],nums[i+1],ops[i])
                    nums[i] = res
                    nums.pop(i+1)
                    ops.pop(i)
                    i-=1
                    #print("calc : ",i,nums, ops)
                i+=1
        candi = abs(nums[0])
        #print(candi)
        max_candi = max(max_candi, candi)
    answer = max_candi
    return answer