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

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/67257

프로그래머스

 

2. 접근

개인적으로 어려웠다,,,,

1. expression에서 수식을 받아와서, st에 없는 연산자면, st에 넣어준다

2. st에 있는 연산자들에 permutation(순열)을 통해서 나올 수 있는 우선순위들을 전부 구한다

3. expressions 라는 새로운 배열에 숫자들은 묶고 ( ex - 1 0 0 은 100으로 묶어서 ) , 연산자는 연산자로 해서 배열에 넣어준다

4. 피연산자들을 for문으로 가져오면서, expressions은 queue에 넣어놓고, queue에서 하나씩 데이터를 뽑되 그게 연산자면 cal method를 실행시킨다

 

내가 생각하기에 간단하면서도 떠올리기 힘들었던 점은,

expressions = tk

이 부분이다.

예를들면, 100 - 200 이 cal 메소드를 호출해서 -100이라는 결과가 만들어져 tk에 들어있다면 이를 바탕으로 expressions를 새롭게 구성을 해야한다!!! 아니면 expressions은 -100이 만들어졌음에도 불구하고 100 - 200 이런식으로 데이터가 들어있을것이기 때문이다.

[ 배열을 치환해줘야 한다 ]

 

로직 자체는 떠올리기 쉽지만, 어떻게 구현해야할지에 대해서 고민하는데 시간이 좀 걸렸다..

 

3. 풀이

from itertools import permutations as pm
from collections import deque

def cal(a,b,oper):
    if oper == '-':
        return a - b
    elif oper == '*':
        return a * b
    elif oper == '+':
        return a + b

def solution(expression):
    
    st = []
    for e in expression:
        if (e in ['-', '*', '+']) and e not in st:
            st.append(e)
    
    # 우선순위 나오는 경우의 수
    express = list(pm(st,len(st)))
    
    ans = 0
    for i in express:
        expressions = []
        val = ''
        for ex in expression:
            if ex not in ['-', '*', '+']:
                val += ex
            else:
                expressions.append(int(val))
                expressions.append(ex)
                val = ''
    
        if val != '':
            expressions.append(int(val))
        
        for op in i:
            print("op :", op)
            q = deque(expressions)
            print("q :", q)
            tk = []
        
            while q:
                data = q.popleft()
                print("data :",data)
                if data == op:
                    last = tk.pop()
                    val = q.popleft()
                    print("last {} oper {} op {}".format(last, val, op))
                    tk.append(cal(last,val,op))
                else:
                    tk.append(data)
                print("tk :", tk)
            expressions = tk
        
        res = abs(expressions[0])
        print(res)
        ans = max(res,ans)
    return ans