사용자 도구

사이트 도구


ps:problems:programmers:67257

문제제목

ps
링크programmers.co.kr/…
출처프로그래머스
문제 번호67257
문제명수식 최대화
레벨Level 2
분류

브루트포스

시간복잡도O(n)
인풋사이즈n<=100
사용한 언어Python
해결날짜2022/01/10

풀이

  • 세가지 연산자의 가능한 우선순위는 총 3!=6가지이다. 그냥 이 6가지 조합에 대해서 전부 식을 계산해보고 최댓값을 구하면 된다.
  • 식을 계산하는 것은 스택을 써서 정석적으로 구현할 수도 있지만, 식의 형태가 단순하기 때문에, 그냥 연산자를 갖고서 문자열을 split한 뒤에, 분할된 각 문자열들에 대해서 다시 재귀적으로 값을 계산하고 마지막에 합쳐주는 방법으로도 충분하다.
    • eval을 쓰면 더 간단하게도 구현 가능하지만 eval은 최대한 쓰지 않기로 했기 때문에 그 방법은 패스

코드

"""Solution code for "Programmers 67257. 수식 최대화".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/67257
- Solution link: http://www.teferi.net/ps/problems/programmers/67257
"""

import functools
import itertools
import operator

OPERATORS = (('*', operator.mul), ('+', operator.add), ('-', operator.sub))


def solve(expression, operators, i):
    if expression.isdigit():
        return int(expression)
    symbol, op = operators[i]
    sub_expressions = expression.split(symbol)
    return functools.reduce(
        op, (solve(x, operators, i + 1) for x in sub_expressions))


def solution(expression):
    return max(
        abs(solve(expression, p, 0)) for p in itertools.permutations(OPERATORS))

토론

댓글을 입력하세요:
N᠎ C N I U
 
ps/problems/programmers/67257.txt · 마지막으로 수정됨: 2022/01/10 04:51 저자 teferi