[프로그래머스 Lv.2] 수식 최대화 (Python)

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

프로그래머스

풀이

레벨 2 문제치고는 구현하는데 조금 어려움이 있었다. 개인적으로 레벨 3 정도는 되어야 하지 않나라는 생각이 들 정도로 어려움이 있었다.

우선 문제 풀이는 아래와 같은 순서로 진행하였다.

1. 주어진 문자열을 피연산자와 연산자로 분리하여 배열에 저장, 동시에 사용되는 연산자들을 순열로 조합하기 위해 연산자들만 따로 저장
2. 연산자들로 이루어진 조합을 permutation을 사용하여 생성
3. 조합을 순회하며 각 연산자를 우선순위 순으로 계산
4. 3에서 계산한 값을 절대값으로 변경하고 최댓값이라면 기록
5. 3,4를 반복하여 최종적으로 나온 최댓값을 반환

from itertools import permutations

def solution(expression):
    answer = 0 # 최대값을 저장할 변수
    expression, operators = parse_expression(expression) # 1번 과정 수행

    for order in permutations(operators): # 순열을 사용하여 우선순위의 조합을 하나씩 순회 
        tmp = expression # 계산을 위해 tmp에 계산할 피연산자와 연산자 배열을 복사
        for operator in order: # 우선순위 대로 특정 연산자를 순회
            while operator in tmp: # 특정 연산자가 남아있으면 계속 반복
                idx = tmp.index(operator) # 특정 연산자의 위치를 알아냄
                tmp = tmp[:idx-1] + [calc(tmp[idx-1:idx+2])] + tmp[idx+2:] # 특정 연산자 위치의 계산을 진행 후 원래 배열에 저장
        answer = max(answer, abs(tmp[0])) # 계산을 마쳤으면 최대값을 저장

    return answer

def parse_expression(expression): # 1번 과정을 수행할 함수
    expression_arr = [] # 주어진 문자열을 피연산자와 연산자로 분리하여 저장할 배열
    operators = set() # 동시에 사용되는 연산자들을 순열으로 조합하기 위해 연산자들만 중복 제외하여 저장할 집합
    
    operand = "" # 피연산자를 기록해둘 변수
    for i in range(len(expression)):
        cur = expression[i] # 현재 위치의 문자
        if cur.isdigit(): # 숫자면 연산자가 아니므로
            operand += cur # 변수에 기록
        else: # 숫자가 아니면 연산자이므로
            expression_arr.append(int(operand)) # 이전까지 기록해두었던 피연산자들을 배열에 저장
            expression_arr.append(cur) # 연산자를 배열에 저장
            operators.add(cur) # 연산자 집합에 저장
            operand = "" # 피연산자를 저장하였으므로 초기화
    expression_arr.append(int(operand)) # 마지막에 남은 피연산자도 저장
    
    return expression_arr, list(operators)

def calc(target): # 3번 과정을 수행할 함수
    operand1, operand2 = target[0], target[2]
    operator = target[1]
        
    if operator == "+": # 연산자가 "+"인 경우 덧셈 연산
        return operand1 + operand2
    
    elif operator == "-": # 연산자가 "-"인 경우 뺄셈 연산
        return operand1 - operand2
        
    else: # 연산자가 "*"인 경우 곱셈 연산
        return operand1 * operand2