[Python][프로그래머스] 수식 최대화 / 완전탐색, 구현(Lv2)

🖇️ 링크 

프로그래머스

---

🗒️ 파이썬 코드 풀이

from itertools import permutations

def solution(expression):
    answer = 0

    # 피연산자(operand) - 연산자(operator) 분리 
    operator = []
    lst_expression = list(expression)

    for idx,op in enumerate(lst_expression):
        if op in '+-*': 
            operator.append(op)
            lst_expression[idx] = " "
            
    operand = ("".join(lst_expression)).split(" ")
    operand = list(map(int,operand))

    # 연산자 우선순위 정하기 
    for ops in permutations(["-","+","*"],3):
        operators = operator[:]
        operands = operand[:]
        
        # 우선순위에 따른 값 구하기
        for i in range(3):
            op = ops[i]
            while op in operators:
                k = operators.index(op)
                
                if op == "-":
                    operands[k] = operands[k] - operands[k+1]
                elif op == "+":
                    operands[k] = operands[k] + operands[k+1]
                elif op == "*":
                    operands[k] = operands[k] * operands[k+1]
                
                operands.pop(k+1)
                operators.pop(k)

        answer = max(answer,abs(operands[0]))  
    
    return answer

 

1. 우선 연산자와 피연산자를 나눠준다. 

• 나눠주는 방식은 다양하다 
• 내 풀이에서는 연산자 먼저 걸러내고, 리스트로 변환 후 join과 split으로 하였다.

2. 연산자의 우선순위를 정한다.

• 순열로 완전 탐색
• 순열 조합으로 반복문 
• operands와 operators 리스트를 dep copy로 새로 만들어줘야 한다.

3. 연산자 ( "-", "+", "*" )   총 3개로, 반복문을 돌린다 .

 

4. 연산자에 따라 값을 계산하고, operands의 값들을 갱신해준다. 

 

5.  (2. 연산자의 우선순위)의  반복문을 돌릴 때마다 answer의 최대값을 비교한다.

 

 

 

시간 복잡도 O( N ) 

• 연산자 우선순위 탐색 O(6)
• 연산자 순열에 대해 수식 계산 O(N)

 

---

🗒️ 잘 못 된 접근 방법

def solution(expression):
    answer = 0

    # 피연산자(operand) - 연산자(operator) 분리 
    operator = []
    lst_expression = list(expression)

    for idx,op in enumerate(lst_expression):
        if op == '+' or op == '-' or op == '*':
            operator.append(op)
            lst_expression[idx] = " "
            
    operand = ("".join(lst_expression)).split(" ")
    operand = list(map(int,operand))

    # 2차원 (max,mx) DP 테이블 각각 생성
    n = len(operand)
    min_dp = [[float('inf')] * n for _ in range(n)]
    max_dp = [[-float('inf')] * n for _ in range(n)]
    
        
    # 초기값 설정 
    for q in range(n):
        min_dp[q][q] = operand[q]
        max_dp[q][q] = operand[q]
        
    # DP 테이블 갱신
    for length in range(2,n+1): 
        for i in range(n - length + 1):
            j = i + length - 1
            for k in range(i,j): 
                if operator[k] == "-" : 
                    max_dp[i][j] = max(max_dp[i][j], max_dp[i][k] - min_dp[k+1][j])
                    min_dp[i][j] = min(min_dp[i][j], min_dp[i][k] - max_dp[k+1][j])
                elif operator[k] == "+" :
                    max_dp[i][j] = max(max_dp[i][j], max_dp[i][k] + max_dp[k+1][j])
                    min_dp[i][j] = min(min_dp[i][j], min_dp[i][k] + min_dp[k+1][j])
                elif operator[k] == "*" :
                    mx1,mx2,mn1,mn2 = max_dp[i][k], max_dp[k+1][j], min_dp[i][k], min_dp[k+1][j]
                    max_tmp_result = max([mx1*mx2, mx1*mn2, mn1*mx2, mn1*mn2])
                    min_tmp_result = min([mx1*mx2, mx1*mn2, mn1*mx2, mn1*mn2])
                    max_dp[i][j] = max(max_dp[i][j], max_tmp_result)
                    min_dp[i][j] = min(min_dp[i][j], min_tmp_result)
                    
    answer = max(abs(max_dp[0][-1]), abs(min_dp[0][-1]))
    
    return answer

 

• 바로 최근에 사칙연산이라는 문제를 풀었고, 이 문제의 업그레이드 버전으로 생각했다.
• 내가 풀이한 방식은 2차원 DP 배열로, 연산자의 우선순위가 아니라 괄호 우선순위의 문제이다. 
  • 괄호 우선순위 예시는 아래와 같다.
    • (((50*6)-3)*2) 이런 식으로 괄호를 적적하게 배치하여 최대값 구함
• 잘 못된 내 풀이로 하면 괄호 우선순위에서의 최대값이 나온다.
• 그렇다면 괄호도 우선순위를 두기 때문에 연산자 우선순위와 똑같지 않을까 ??
  • 괄호의 우선순위와 연산자 우선순위에 다른 것이 있다.
  • 괄호 같은 경우, 연산자와 상관없이 어디에나 우선순위를 둘 수 있다.
  • 반면 연산자 우선순위는 +, - , * 의 우선순위를 둔다.
  • 때문에 위에 연산자 우선순위로 위의 예시를 풀리하면 아래와 같이 된다.
    • ((50*6)-(3*2)) 
    • 1 번째 우선 순위 *(곱하기) , 2번째 우선 순위 - (마이너스)
    • 곱하기 연산자 모두 처리 후, 마이너스 연산 처리
• 위와 같은 이유로 나의 코드는 문제에 요구하는 사항에 충족하지 못한다.

 

 

[Python][프로그래머스] 사칙연산 / DP (Lv4)

괄호 우선순위 문제 참고

---

📌  문제 코멘트 

이 문제를 포스팅 하는 이유는 다음과 같다.

• DP 문제와 착각하여 잘 못 풀이 (연산자 우선순위 문제에 괄호 문제 풀이 적용)
• 연산자와 피연산자를 리스트로 계산하는 과정
  • 해당 과정에서 operands, operator 리스트의 값을 변경 및 삭제한다.
  • 이런 비슷한 문제의 유형을 많이 풀어보지 않았다. (처음 봤을때 어려워 보였음)

---

ℹ️ 풀이 과정

---

📚  문제