수식 최대화

문제풀이

from itertools import permutations
import re
import queue
import copy

def solution(expression):
    answer = 0
    ops = []
    
    q = []
    
    numbers = re.split("[-, +, *]", expression)
    expression = list(expression)
    for num in numbers:
        q.append(int(num))
        for op in expression[:]:
            if op in ['-', '+', '*']:
                ops.append(op)
                q.append(expression.pop(0))
                break
            else:
                expression.pop(0)
                
    ops = set(ops)            
    op_lists = list(permutations(ops, len(ops)))
    for op_list in op_lists:
        new_q = q[:]
        for op in op_list:
            qx = []
            while(len(new_q)>0):
                num_or_op = new_q.pop(0)
                if num_or_op == op:
                    if op == '-':
                        qx.append(qx.pop() - new_q.pop(0))
                    elif op == '+':
                        qx.append(qx.pop() + new_q.pop(0))
                    else:
                        qx.append(qx.pop() * new_q.pop(0))
                else:
                    qx.append(num_or_op)
            new_q = qx[:]
            if len(new_q) == 1:
                result = abs(new_q[0])
                if answer < result:
                    answer = result
            
                      
    return answer

알고리즘

Queue

이 문제에서 Queue를 활용했다. 두 개의 Queue를 만들고 하나의 Queue에는 수식을 저장하고 다른 Queue에는 이전 Queue에서 하나씩 검사해가면서 연산자 우선순위에 맞게 계산을 하고 저장한다. 이 과정을 반복하면서 가장 큰 값을 찾아낸다.

Queue는 리스트로 구현했다.

itertools.permutations(iterable, r=None)

permutation은 서로 다른 n개(iterable) 중 r개를 골라 순서를 고려해 나열한 경우의 수이다. 이를 순열이라고 한다.

 

eval()

다른 사람 풀이 중 eval함수를 사용한 좋은 예제가 있어 소개한다.

eval() 함수는 수식(문자열)을 입력받으면 해당 수식의 계산 결과를 반환한다.

예를 들어,

>>>x = 1
>>>eval('x+1')
2

출처

문제: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

코딩테스트 연습

파이썬 자료구조와 알고리즘 - 미아 스타인 저/최길우 역

Do it! 자료구조와 함께 배우는 알고리즘 입문 : 파이썬 편 - 시바타 보요 저/강민 역