수식 최대화[2020 카카오 인턴]

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

코딩테스트 연습 - 수식 최대화

프로그래머스 2단계 정도의 문제이다.(생각보다 난이도가 낮구나...)

 

코드 먼저 살펴보자!

from itertools import permutations
import re

def calculate(op, num1, num2) :
  result = 0
  if op == '*' :
    result = int(num1) * int(num2)
  if op == '+' :
    result = int(num1) + int(num2)
  if op == '-' :
    result = int(num1) - int(num2)
  return result

def solution(expression) :
  temp = []
  result = []
  last_index = 0
  has = set()
  
  # re.split('(\D)', expression) 숫자가 아닌것을 기준으로 split 한다, \d면 숫자겠지???
  for i in range(len(expression)) :
    if expression[i] in ['*', '+', '-'] :
      temp.append(expression[last_index:i])
      temp.append(expression[i])
      has.add(expression[i])
      last_index = i + 1
  if last_index != len(expression) :
    temp.append(expression[last_index:])
    last_index = 0
  
  priority_list = list(map(list,permutations([*has], len([*has]))))

  for priority in priority_list :
    l = list(temp)

    for op in priority :
      stack = []
      while (len(l) != 0) :
        tmp = l.pop(0)
        if tmp == op :
          stack.append(calculate(op, stack.pop(), l.pop(0)))
        else :
          stack.append(tmp)
          
      l = stack
    
    result.append(abs(l.pop(0)))
      
  return max(result)

print(solution("100-200*300-500+20"))
print(solution("50*6-3*2"))

 

접근 방법

* 우선순위를 나열해줄 순열 코드가 필요할것 같았다(permutations(배열, 길이))

* 전위, 중위, 후위 표현식을 구현할때 사용하는 stack을 사용해야겠다고 생각이 들었다.

 

막혔던 부분

* 우선순위가 정해진 숫자 기호별로 접근을 할때 값을 다시 가져오고 계산하는 부분에서 애를 먹었다.

* 입력받은 표현식을 숫자, 연산기호 별로 나누는데 애를 좀 먹었었다.(re 내장 라이브러리를 나중에 알았다)

 

처음 접했을때는 굉장히 난감 했는데 지하철에서 코딩하면서 접근 방법을 떠올렸던 문제였다. 

보석 쇼핑에 비해서는 쉬웠던것 같다.