프로그래머스 67257 : 수식 최대화

수식 최대화

 

 

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

원래 이젠 티스토리에 알고리즘 관련된 글은 안 쓰려고 했는데 이건 어렵고 새로 써 본 기능이 있어서 적어놔야 할 것 같다..

 

핵심 기능 : itertools.permutations

 

이 기능은, 순열을 돌아주는 기능이다. 굳이 factorial(n)만큼 경우의 수를 돌릴 필요가 없게 해 주는 것이다.

ex) permutations(['+', '-', '*'], 3) -> (+,-,*) (+,*,-) (-,+,*) (-,*,+) (*,+,-) (*,-,+) 리스트를 뽑아준다.

요긴하게 잘 썼다.

 

풀이는 다음과 같이 했다.

from itertools import permutations
import heapq


# 계산식을 [ n1, op1, n2, op2, n3 ... ] 형식으로 분리하기
# ex) ['1', '+', '2', '-', '3', '*']
def get_splitted_expression(expression):
    num_list = []
    temp_str = ""
    for char in expression:
        if char == '-' or char == '+' or char == '*':
            num_list.append(temp_str)
            num_list.append(char)
            temp_str = ""
        else:
            temp_str += char
    num_list.append(temp_str)
    return num_list


def calc_by_splitted_expression_and_operator_list(splitted_expression, operator_list):
    result = list(splitted_expression)
    for op in operator_list:
        idx = 0
        while idx < len(result):
            if result[idx] == op:
                # result[idx] == op : 현재 작업해야하는 연산자임. 연산하면 됨
                num1 = result.pop(idx - 1)
                result.pop(idx - 1)
                num2 = result.pop(idx - 1)
                now_expression = str(num1) + op + str(num2)
                result.insert(idx - 1, eval(now_expression))
                idx -= 1
            idx += 1

    # 절댓값으로 계산 하도록 제시되어 있었으므로
    return abs(int(result[0]))


def solution(expression):
    answer = []
    operator_list = permutations(['+', '-', '*'], 3)
    splitted_expression = get_splitted_expression(expression)

    for ops in operator_list:
        heapq.heappush(answer, calc_by_splitted_expression_and_operator_list(splitted_expression, ops) * -1)

    return heapq.heappop(answer) * -1

1. 연산자 종류 구분하기

처음에는 문장 내의 연산자 개수를 구해서 permutations 하도록 했는데, 실행시간이 큰 차이가 없어서 그냥 간소화를 위해 빼버렸다.

from itertools import permutations

def solution(expression):
    # ...
    
    operator_list = permutations(['+', '-', '*'], 3)
    
    # ...

이 구간에 해당한다.

 

2. 수식 분리하기

수식을 어떻게 분리할지 고민을 좀 했는데, 난 index 기반으로 풀어나가려고 했기 때문에 num1, op, num2 형식으로 분리해줬다.

# 계산식을 [ n1, op1, n2, op2, n3 ... ] 형식으로 분리하기
# ex) ['1', '+', '2', '-', '3', '*']
def get_splitted_expression(expression):
    num_list = []
    temp_str = ""
    for char in expression:
        if char == '-' or char == '+' or char == '*':
            num_list.append(temp_str)
            num_list.append(char)
            temp_str = ""
        else:
            temp_str += char
    num_list.append(temp_str)
    return num_list

이 구간에 해당한다.

 

3. 연산자의 리스트로 1차 반복

우선순위에 따라 계산해주기 위해 맨 앞의 연산자로 반복을 돌려줬다.

def calc_by_splitted_expression_and_operator_list(splitted_expression, operator_list):
    for op in operator_list:
    	# todo ...

이 구간에 해당한다.

 

4. 수식의 리스트로 2차 반복

수식의 내용이 연산자인지 수인지 구분시켜 계산해주기 위한 반복문이다.

def calc_by_splitted_expression_and_operator_list(splitted_expression, operator_list):
    result = list(splitted_expression)
    for op in operator_list:
        idx = 0
        while idx < len(result):
            if result[idx] == op:
                # result[idx] == op : 현재 작업해야하는 연산자임. 연산하면 됨
                num1 = result.pop(idx - 1)
                result.pop(idx - 1)
                num2 = result.pop(idx - 1)
                now_expression = str(num1) + op + str(num2)
                result.insert(idx - 1, eval(now_expression))
                idx = -1
                # 개선사항 : idx = -1 -> idx -= 1
            idx += 1

이 구간에 해당한다.

솔직히 말해서, 이 구조는 시간복잡도상으로 굉장히 불리하다. 작업이 끝나면 첫 번째 인덱스부터 다시 스캔을 해줘야하기 때문이다. 문제 자체가 길지 않았기 때문에 가능했던 일이다.

 

근데 글을 쓰면서 느낀건데, idx = -1 해줄 필요 없이 idx -= 1 해줘도 풀릴 것 같다. 해봤는데 된다! 이렇게 되면 그다지 불리하지 않은 수준의 시간복잡도가 완성되었다. 확실히 되풀이해보는건 중요한 것 같다.

 

5. 문제의 조건에 따라, 절댓값으로 return

단순하지만, 중요한 부분이다. 문제의 성패를 가르는 구간이기 때문이다.

def calc_by_splitted_expression_and_operator_list(splitted_expression, operator_list):
	# ...
    
    # 절댓값으로 계산 하도록 제시되어 있었으므로
    return abs(int(result[0]))

이 구간에 해당한다.

 

 

6. solution으로 돌아와서, permutation 완료한 리스트로 반복 후, 최댓값 return

마무리 스텝이다. 메인 메소드는 심플할수록 좋다고 생각한다.

import heapq

def solution(expression):
    answer = []
    operator_list = permutations(['+', '-', '*'], 3)
    splitted_expression = get_splitted_expression(expression)

    for ops in operator_list:
        heapq.heappush(answer, calc_by_splitted_expression_and_operator_list(splitted_expression, ops) * -1)

    return heapq.heappop(answer) * -1

 

이렇게 풀이를 했는데....

2시간 30분정도 걸렸다. permutations 기능을 인터넷에 검색해봐서 다행이지 아니었으면 여기에서 또 추가적인 시간 소모가 있었을 것이다. 절망적으로 느린 속도다. 아직도 갈 길이 엄청 멀다는 뜻이다.

이런 문제는 30분 내외로 풀 수 있도록 숙련도를 올려야 하는데.. 알고리즘이라는 것 자체가 범위가 참 넓고 생각해야 할 게 많아서 실력이 느는 속도가 막 빠르지가 않다. 코딩테스트 봐야 하는 시간이 올 때까지 실력을 충분히 끌어올릴 수 있을지가 걱정이 된다.