[2020 카카오 인턴십 / 프로그래머스] 67257번 : 수식 최대화 (다시)

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

 

Lv2 문제다!

참고한 블로그

 

문제 이해 

최대 3개의 연산자(*, +, -)의 우선순위를 매겨서 계산한 결과 중 절댓값의 최대를 구하는 문제다

연산자의 개수가 몇개 안되므로 이는 permutations을 통해 정하면 된다고 생각했다

문제는 우선순위에 따라 식을 계산하는 건데, 여기에서 막혔었다 

각 순열에 대해서 우선순위에 따른 값을 abs로 절댓값으로 바꾼다음 그 중 최댓값을 반환하면 된다

 

풀이 이해 

• expression에서 숫자와 연산자를 따로 분리하기 위해 li 스택을 이용한다 ('100', '+', '200) 
• 3개의 연산자 중 식에 없는 연산자는 제거한다 
• permutations 함수를 이용해 임의의 연산자 우선순위를 구한다 
• 우선순위에 맞춰서 식을 계산한다(여기가 가장 어렵다)
• 계산한 결과를 abs로 절댓값으로 바꿔준다
• answer와 result 중 최댓값을 누적한 후 반복문이 끝나면 해당 answer를 반환한다 

 

- 정답 풀이 : 

from itertools import permutations
from collections import deque

def solution(expression):
    answer = 0
    ops = ["*", "+", "-"]
    
    # 스택 생성
    li = []
    s = 0
    for i, v in enumerate(expression):
        if v in ["*", "+", "-"]:
            li.append(expression[s:i])
            li.append(v)
            s = i + 1
    else:
        li.append(expression[s:])
    
    # expression에 없는 연산자는 ops에서 제거
    for op in ops:
        if op not in expression:
            ops.remove(op)
            
    # ops에 있는 연산자로 구성할 수 있는 모든 우선순위 생성
    primarity = permutations(ops)
    
    for case in primarity: # 최대 6가지의 연산자 우선순위 조합
        stacks = [deque(li), deque()]
        t1 = 1
        for c in case: # 각 경우에서 연산자 처리
            t1 = (t1+1) % 2 # 스택 토글 변수
            t2 = (t1+1) % 2
            while len(stacks[t1]):
                item = stacks[t1].popleft()
                if len(stacks[t2]) and stacks[t2][-1] == c:
                    c = stacks[t2].pop()
                    n = stacks[t2].pop()
                    item = str(eval(str(n)+c+str(item)))
                stacks[t2].append(item)
            
        result = stacks[len(ops)%2].pop()
        result = abs(int(result))
        answer = max(answer, result)
            
    return answer