(Python/Python) 프로그래머의 Lv2 – 최대화 공식 (카카오 인턴십)

by

문제 설명

저는 IT 벤처 캐피털 회사를 운영하고 있습니다.

Ryan은 우승자에게 상품을 제공하는 연례 내부 해커톤을 개최합니다.


이전 콘테스트와 달리 다음과 같은 방식으로 우승자에게 수여되는 상금을 결정하려고 합니다.


해커톤의 모든 참가자에게는 숫자와 세 개의 산술 문자(+, -, *)로 구성된 산술 공식이 제공됩니다.

참가자는 전달된 수식에 포함된 연산자의 우선 순위를 자유롭게 재정의하여 만들 수 있는 가장 큰 숫자를 제출해야 합니다.


그러나 새로운 연산자 우선 순위를 정의할 때 동일한 순위의 연산자가 있을 수 없습니다.

다시 말해서, + > – > * 또는 – > * > + 예를 들어 연산자 우선 순위를 정의할 수 있습니다.

+,* > – 또는 * > 둘 이상의 연산자가 + 및 -와 같이 동일한 순위를 갖도록 연산자 우선 순위를 정의할 수 없습니다.

식에 두 개의 연산자가 포함된 경우 정의할 수 있는 연산자 우선 순위의 가능한 조합은 2!
= 2, 연산자가 3개면 3!
= 6개의 조합이 가능합니다.


계산 결과가 음수일 경우 그 숫자의 절대값을 환산하여 제출하며, 가장 큰 숫자를 제출한 참가자를 우승자로 선정하고, 우승자가 제출한 숫자를 당첨금으로 지급 .

예를 들어, 참가자들 사이 Neo가 다음 수식을 전달한다고 가정합니다.

“100-200*300-500+20”

일반적으로 덧셈과 뺄셈은 수학과 전산학에서 약속한 연산자 우선순위에 따라 동등하며, 곱셈은 덧셈과 뺄셈보다 우선순위가 높습니다.

* > +,- 우선 순위가 정의됩니다.


게임의 규칙에 따라 + > – > * 또는 – > * > + 예를 들어 연산자 우선 순위를 정의할 수 있습니다.

+,* > – 또는 * > +,- 다음과 같이 두 개 이상의 연산자가 동일한 순위를 갖도록 연산자 우선 순위를 정의할 수 없습니다.


수식에 3개의 연산자가 있는 경우 가능한 연산자 우선 순위 조합은 3!
= 6, 여기서 + > – > * 연산자 우선 순위를 로 설정하면 결과 값은 22,000원입니다.


반면에 * > + > – 연산자 우선 순위가 설정되면 수식의 결과 값은 -60,420이지만 규칙에 따라 우승 상금은 절대 값인 60,420원입니다.

참가자에 대한 수식이 포함된 문자열 표현식을 인수로 주어 승리 시 얻을 수 있는 최대 상금을 반환하는 솔버 기능을 완성합니다.

한계

  • expression은 길이가 3 이상 100 이하인 문자열입니다.

  • 표현식은 적절한 중위 표기법(연산의 두 대상 사이에 연산자 기호를 사용하는 방법)으로 표현되는 표현식으로 숫자와 3개의 연산자(+, -, *)로만 구성되며 공백이나 괄호는 사용하지 않습니다.

    유효하지 않은 표현식은 입력으로 제공되지 않습니다.

    • 다시 말해서, “402+-561*”과 같은 유효하지 않은 수식은 올바른 중위 표기법이 아니기 때문에 제공되지 않습니다.

  • 식의 피연산자는 0에서 999 사이의 숫자입니다.

    • 다시 말해서, “100-2145*458+12″와 같이 피연산자가 999개 이상인 표현식은 입력으로 제공되지 않습니다.

    • “-56+100″과 같이 피연산자가 음수인 표현식도 입력으로 제공되지 않습니다.

  • 식에는 하나 이상의 연산자가 포함됩니다.

  • 연산자 우선 순위가 적용되는 방식에 관계없이 식의 중간 평가 및 최종 결과의 절대값은 263입니다.

    – 1 이하를 입력합니다.

  • 같은 연산자 사이에서는 전자가 우선합니다.

입력 및 출력 예

표현하다 결과
“100-200*300-500+20” 60420
“50*6-3*2” 300

솔루션.py

이 문제를 해결하기 전에 평가 기능에 대해 알아보기필요합니다.

eval(expression) 함수란 무엇입니까?

매개변수로 받기 연산식(산술식이 포함된 문자열)을 실행하여 계산된 숫자를 반환하는 함수보지 않았다.

예를 들어 eval(“100+400”)을 실행하면 문자열로 받은 “100+400″을 평가하고 500을 반환합니다.

eval("100+400") // 500

문제를 풀다

  1. 인수 set(re.findall(“\D”, expression)) 로 받은 표현식에 포함된 연산자만 반복 없이 추출합니다.

  2. 추출된 연산자는 우선 순위 연산자 순열과 순열 함수의 조합을 만드는 데 사용됩니다.

  3. dfs 알고리즘을 통해 생성된 우선 순위 연산자 순열과 조합을 차례로 순회하여 절대값이 가장 큰 숫자를 반환합니다.

정답 코드

import re
from itertools import permutations

def solution(expression):
    answer = 0
    operator = set(re.findall("\D", expression)) # expression에 포함된 연산자만을 추출 (중복x)
    priorities_operators = list(permutations(operator, len(operator)))

    for priorities in priorities_operators:
        evaluated_val = int(dfs(expression, priorities, 0))
        answer = max(answer, abs(evaluated_val))

    return answer

def dfs(expression, priorities, depth):
    if depth == len(priorities) - 1:
        return str(eval(expression))
    
    oper = priorities(depth)
    print(expression.split(oper))
    evaluated = eval(
        oper.join(
            (dfs(e, priorities, depth = depth + 1) for e in expression.split(oper))
        )
    )
    
    return str(evaluated)

먼저 순열의 경우할 것이다.


Related Posts: