프로그래머스 수식 최대화(Python)

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

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

하... 이 문제가 레벨 2라는 게 믿기지가 않는다.. 오래 걸렸어도 내가 생각했던 방향대로 끝까지 풀었다는 것에 만족한다. 다른 풀이들을 보니 나처럼 푼 사람이 안 보인다... 하하....

나의 풀이

내 풀이의 순서는 아래와 같다.

1. 연산자들의 모든 우선순위의 경우들을 구한다.
2. 각 우선순위를 적용해서 계산식을 이진트리로 구성한다.
3. 구성한 이진트리에서 postorder 순회를 통해 연산자, (피) 연산자들을 postorder로 스택에 담는다.
4. 스택을 이용해 식을 계산한다.
5. 계산 결과들 중 최댓값을 반환한다.

1. 연산자들의 모든 우선순위 구하기

연산자의 우선순위를 각기 다르게 설정하면 최대 6가지의 경우가 나온다. 6개 정도면 직접 입력해도 된다. 나도 처음에는 그렇게 시작했다. 다 풀고 다른 사람들의 풀이를 보니 permutations를 이용해 6가지를 직접 입력하지 않고 만들어냈다! 그래서 나는 permutations가 무엇인지 알기 위해 파이썬 documentation을 보았다.

https://docs.python.org/ko/3.8/library/itertools.html?highlight=permutation#itertools.permutations 

itertools — 효율적인 루핑을 위한 이터레이터를 만드는 함수 — Python 3.8.13 문서

간단하게 얘기하자면 iterable 한 객체 안에 있는 항목들에 대한 모든 순열들을 튜플의 형태로 담아 반환해준다.

>>> from itertools import permutations
>>> a = permutations([0, 1, 2])
>>> a
<itertools.permutations object at 0x7fe87f21b9f0>
>>> for t in a:
...     a
...
(0, 1, 2)
(0, 2, 1)
(1, 0, 2)
(1, 2, 0)
(2, 0, 1)
(2, 1, 0)

이를 이용해서 연산자들의 모든 우선순위들을 담을 수 있는 코드를 작성할 수 있었다.

from itertools import permutations

def solution(expression):
    answer = []
    priorities = list(permutations(["+", "-", "*"]))

2. 계산식을 이진 트리로 구성

내가 트리를 이용한 풀이 방법이 생각난 이유는 2학년 1학기 때 '자료구조' 시간에 트리를 이용해 계산식을 가지고 뭔가를 했던 기억이 있었기 때문이다. 그래서 트리로 풀어봤는데... 역시 트리를 구성하려니 코드가 길어졌다. 파이썬으로 이진트리를 짠 코드는 아래와 같다.

class Node:
    def __init__(self, _value, _prior=-1):
        self.value = _value
        self.prior = _prior    # 우선순위
        self.left = None
        self.right = None
        
class ExpressionTree:
    def __init__(self, _operations):
        self.operations = _operations
        self.root = None    # 초기에는 루트 노드도 없는 트리다.
        
    def insert(self, _v):
        # Make new Node
        new_node = Node(_v)
        for i in range(len(self.operations)):    # 우선 순위 결정
            if _v == self.operations[i]:
                new_node.prior = i
                break
        
        # Insert new Node to tree
        if self.root is None:
            self.root = new_node
        elif _v not in self.operations:
            pointer = self.root
            while pointer.right is not None:
                pointer = pointer.right
            pointer.right = new_node
        elif self.root.prior <= new_node.prior:    # root's priority is higher than new_node's
            new_node.left = self.root
            self.root = new_node
        else:                                      # root's priority is lower than new_node's
            pointer = self.root
            while pointer.right.prior > new_node.prior:
                pointer = pointer.right
            new_node.left = pointer.right
            pointer.right = new_node

트리에 연산자와 피연산자를 넣으려면 계산식을 피연산자와 연산자로 나눌 수 있어야 한다. 여기서 나는 바로 정규식을 생각해냈다.

import re
from itertools import permutations

def solution(expression):
    answer = []
    p = re.compile('(\+|\*|-)')
    nodes = p.split(expression)
    priorities = list(permutations(["+", "-", "*"]))

3. Postorder로 스택에 담기

postorder는 왼쪽 자식을 방문하고, 오른쪽 자식을 방문한 후 자기 자신을 방문하는 순서로 방문하는 방식이다.

계산식이 postorder를 따른 postfix형태의 계산식으로 변환되면 스택을 이용해 계산할 수 있다는 것이 생각나서 적용했다. 이 기능을 이진트리의 멤버 함수로 구현했다.

class ExpressionTree:            
    def fill_postfix(self, _root, _stack):
        if _root is None:
            return
        else:
            self.fill_postfix(_root.left, _stack)
            self.fill_postfix(_root.right, _stack)
            _stack.append(_root.value)

4. 식 계산하기

먼저 빈 스택을 하나 생성한다. 인자로 받은 postfix 계산식에서 피연산자인 경우 스택에 push 하고 연산자인 경우 스택에서 피연산자 두 개를 pop 해서 계산한 결과를 새로 push 한다. 문제 조건에 맞춰서 연산의 최종 결과의 절댓값을 반환한다.

def eval_postfix(_p):
    stack = []
    for character in _p:
        if character == "+":
            right = stack.pop()
            left = stack.pop()
            stack.append(left + right)
        elif character == "-":
            right = stack.pop()
            left = stack.pop()
            stack.append(left - right)
        elif character == "*":
            right = stack.pop()
            left = stack.pop()
            stack.append(left * right)
        else:
            stack.append(int(character))
    return abs(stack[0])

5. 최종 코드

위에서부터 지금까지 얘기한 과정들을 하나로 모으면 아래의 긴 코드가 된다.

from itertools import permutations
import re

class Node:
    def __init__(self, _value, _prior=-1):
        self.value = _value
        self.prior = _prior
        self.left = None
        self.right = None

class ExpressionTree:
    def __init__(self, _operations):
        self.operations = _operations
        self.root = None

    def insert(self, _v):
        # Make new Node
        new_node = Node(_v)
        for i in range(len(self.operations)):
            if _v == self.operations[i]:
                new_node.prior = i
                break

        # Insert new Node to tree
        if self.root is None:
            self.root = new_node
        elif _v not in self.operations:
            pointer = self.root
            while pointer.right is not None:
                pointer = pointer.right
            pointer.right = new_node
        elif self.root.prior <= new_node.prior:    # root's priority is higher than new_node's
            new_node.left = self.root
            self.root = new_node
        else:                                      # root's priority is lower than new_node's
            pointer = self.root
            while pointer.right.prior > new_node.prior:
                pointer = pointer.right
            new_node.left = pointer.right
            pointer.right = new_node

    def fill_postfix(self, _root, _stack):
        if _root is None:
            return
        else:
            self.fill_postfix(_root.left, _stack)
            self.fill_postfix(_root.right, _stack)
            _stack.append(_root.value)

def eval_postfix(_p):
    stack = []
    for character in _p:
        if character == "+":
            right = stack.pop()
            left = stack.pop()
            stack.append(left + right)
        elif character == "-":
            right = stack.pop()
            left = stack.pop()
            stack.append(left - right)
        elif character == "*":
            right = stack.pop()
            left = stack.pop()
            stack.append(left * right)
        else:
            stack.append(int(character))
    return abs(stack[0])

def solution(expression):
    answer = []
    p = re.compile('(\+|\*|-)')
    nodes = p.split(expression)
    priorities = list(permutations(["+", "-", "*"]))
    # Build Tree
    for prior in priorities:
        tree = ExpressionTree(prior)
        for n in nodes:
            tree.insert(n)
        postfix_items = []
        tree.fill_postfix(tree.root, postfix_items)
        result = eval_postfix(postfix_items)
        answer.append(result)
    return max(answer)

프로그래머스 채점 서버에서 돌려본 결과, 최대 0.72ms, 10.6MB의 자원을 소모했다.

다른 사람의 풀이

여기서의 풀이의 핵심은 우선순위에 맞게 괄호를 붙여준다는 것이다.

우선순위가 낮은 연산자를 기준으로 계산식을 split 해가면서 우선순위가 높은 순서로 괄호를 씌운 새로운 계산식을 만들어내는 방법이다. 계산실을 만들어내면 파이썬의 내장 함수인 eval을 통해 계산한다.

https://programmers.co.kr/learn/courses/30/lessons/67257/solution_groups?language=python3 

프로그래머스

from itertools import permutations
def solution(expression):
    operations = list(permutations(['+', '-', '*']))
    answer = []
    for op in operations:
        a = op[0]
        b = op[1]
        temp_list = []
        for e in expression.split(a):
            temp = [f"({i})" for i in e.split(b)]
            temp_list.append(f'({b.join(temp)})')
        answer.append(abs(eval(a.join(temp_list))))
    return max(answer)

프로그래머스 채점 서버에서 돌려본 결과, 최대 0.46ms, 10.3MB의 자원을 소모했다.

나의 풀이보다 약 0.3ms 빠르고 0.3MB 덜 사용한다. 하지만 어떤 사람이 알려준 바에 따르면 eval 내장 함수는 보안 상의 문제가 발생할 수 있기 때문에 코딩 테스트 같은 곳에서 안 쓰는 게 좋다고 한다.

 

자료구조 시간에 배운 것을 적용한 점에서는 좋았던 문제지만 이렇게 보다 쉽게 풀어나갈 수 있었다는 것에 살짝 허무함이 느껴지기도 했다...