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

---

문제설명

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

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

사고과정

• 느낌이 스택과 완전탐색을 활용한 문제라고 생각했다. DFS를 활용해서 연산 우선순위 완전탐색을 잘 구현하긴 했지만 우선순위 연산에 따라 스택을 활용해서 계산을 계속 갱신하는 데 실패했다.. 대체 스택을 어떻게 활용해야 할까.. 어려워서 1시간 넘게 고민한 후 결국 구글링의 도움을 받았다.
• 결과적으로 DFS 탐색으로 완전탐색으로 구현해도 되었지만 여기서는 permutations 함수를 사용하는 것이 코드가 더 간결해진다고 생각했다. 굳이 DFS 탐색으로 구현해볼까..! 했는데 코드가 너무 장황해질 것 같아서 나도 사람들처럼 permutations를 사용하기로 했다.
• 그리고 주어진 문자열에서 숫자완전체 따로 연산자 따로 변환하도록 했어야 했는데, 예를 들어, '100+200-300' 이 있으면 이것을 [1,0,0,+,2,0,0,-,3,0,0] 이 아니라 [100, +, 200, -, 300] 이런식으로 말이다. 이렇게 구현하는 방법은 스스로 성공해냈다.
• 또 문제에서 +, -, * 연산 3가지만 등장한다고 했고 문자열에서 연산 3가지 중 없는 연산이 있다고 하더라도 구현하는 함수에서 자동으로 무시하기 때문에 애초에 +, - , * 연산 3가지가 있다고 가정하고 경우의 수를 탐색하면 된다(물론 주어진 문자열에 존재하는 연산만 필터링해서 경우의 수를 탐색할 수도 있긴함. 그런데 이렇게 하면 코드가 더 길어질 것이라고 생각)
• 내가 구현하지 못한 부분의 핵심은 16~25번 라인의 코드이다. 주어진 연산 우선순위의 원소대로 loop를 돌면서 해당 우선순위의 연산일 때만 계산을 적용하고 나머지는 스택에 넣어버린다. 그리고 다시 스택을 array로 갱신하고 이를 반복한다. 이분의 풀이를 보면서 매우 감탄했다.. 어찌 이런 아이디어를 떠올리셨는지.. 리스펙한다.. 도움 감사합니다! 코드도 매우 간결하고 해서 참고한 풀이를 많이 참조했다. 다른 점이라고 한다면 어차피 중위 표기식으로 연산을 수행하기 때문에 eval 함수를 사용했다는 점

풀이(스스로 못 푼 풀이)

from itertools import permutations

def calculate(exp, op):
    array = []
    num = ''
    for x in exp:
        if x.isdigit():
            num += x
        else:
            array.append(num)  # 피연산자 기록
            array.append(x)    # 연산자 기록
            num = ''
    array.append(num)
    
    # 스택을 활용해서 연잔자 순위에 따라 계산 -> 내가 해결하지 못한 부분
    for o in op:
        stack = []  # 현재 연산을 수행하고 난 후의 결과들 기록
        while len(array) != 0:
            tmp = array.pop(0)
            if tmp == o:
                val = eval(str(stack.pop()) + o + str(array.pop(0))) # 이게 핵심..
                stack.append(val)
            else:
                stack.append(tmp)
        array = stack
    return abs(int(array[0]))


def solution(expression):
    op = ['*', '-', '+'] # 어차피 expression에 없는 연산자는 무시되서 계산됨
    op = list(permutations(op, 3))
    answer = 0
    for i in op:
        temp = calculate(expression, i)
        answer = max(answer, temp)
    return answer