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

📕 문제

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

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

 

💡 풀이법

1. 먼저 입력값을 돌면서 연산자와 숫자를 배열로 분류해준다.

2. 가능한 연산자 우선순위의 경우의 수를 순열로 만들어서 for문을 돌면서 완전 탐색한다.

3. 연산 결과를 담을 result 리스트와 남은 연산자를 담을 new_oper 리스트를 만들고 우선순위 리스트를 앞에서부터 돈다. (result리스트에는 미리 첫번째 숫자를 넣어둔다.)

4. 숫자리스트와 연산자 리스트를 카피해서 현재 우선순위에서 사용할 새로운 숫자리스트 number_copy와 새로운 연산자 리스트 operator_copy를 만든다.

5. operator_copy를 돌면서 현재 우선순위 연산자와 일치하면 result에 result 리스트에서 마지막 숫자를 pop해서 계산한 값을 더해주고 일치하지 않으면 그냥 더해주고 현재 연산자도 new_oper에 넣어준다.

6. 우선순위 리스틀 다 돌면 결과값의 절대값을 answer과 비교해서 더 큰 값을 answer에 담는다.

 

from itertools import permutations

def solution(expression):
    answer = 0
    operators = []
    numbers = []
    nums = ''
    for i in expression:
        if i.isdigit():
            nums += i
        else:
            numbers.append(int(nums))
            operators.append(i)
            nums = ''
    numbers.append(int(nums))

    uni = set(operators)
    for priority in permutations(uni, len(uni)):
        operators_copy = operators[:]
        numbers_copy = numbers[:]
        for oper in priority:
            result = [numbers_copy[0]]
            new_oper = []
            for i in range(len(operators_copy)):
                if operators_copy[i] == oper:
                    if operators_copy[i] == '+':
                        num = result.pop() + numbers_copy[i+1]
                    elif operators_copy[i] == '-':
                        num = result.pop() - numbers_copy[i+1]
                    else:
                        num = result.pop() * numbers_copy[i+1]
                    result.append(num)
                else:
                    new_oper.append(operators_copy[i])
                    result.append(numbers_copy[i+1])
            numbers_copy = result
            operators_copy = new_oper
        answer = max(answer, abs(numbers_copy[0]))

    return answer