2020 카카오 인턴십_수식 최대화(파이썬, Python)

[문제 출처]

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

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

---

이 문제를 두 단계로 나눠서 생각했다.

1. 순열을 이용해서 연산자 우선순위 경우의 수 구하기

2. 우선순위에 맞게 연산 수행하기

 

1단계 - 순열을 이용해서 연산자 우선순위 경우의 수 구하기

 

어떤 우선순위에 따라 계산을 해야 상금이 최대가 되는지 모른다.

따라서 모든 경우의 수를 구할 필요가 있으며 이를 위해 순열을 이용했다.

❗️연산자의 우선순위가 중요(=순서가 중요) 하므로 조합이 아닌 순열을 이용한다.

❗️python에서 순열을 간단하게 계산하기 위해 라이브러리를 이용했다.

 

from itertools import permutations # 라이브러리는 이렇게 호출하면 된다.

 

2단계 - 우선순위에 맞게 연산 수행하기

 

1단계에서 구한 모든 경우의 수를 대입하며 상금을 계산한다.

연산자 우선순위가 정해졌으므로 우선순위가 높은 순서대로 연산을 수행하면 된다.

 

계산을 편리하기 위해 숫자와 연산자를 각각 리스트로 만들었다.

(이때 정규 표현식을 이용했다.)

 

numList = list(map(int, re.findall("[0-9]+", expression))) # 숫자를 추출한 후 numList에 저장
opList = re.findall("[^0-9]+", expression) # 연산자를 추출한 후 opList에 저장

 

연산을 수행하는 원리는 아래와 같다.

 

numList[opList.index(타깃 연산자)] (타깃 연산자) numList[opList.index(타깃 연산자)+1]

 

ex)

numList = [1, 2, 3]

opList = ['+', '-']

타깃 연산자 = '+'

index = opList.index('+')

 

numList[index] + numList[index+1]

⇒ numList[0] + numList[1]

=> 3

 

연산을 수행한 후 계산된 결과는 타깃 연산자의 인덱스를 이용하여 numList에 삽입하고

numList[index + 1]과 opList[index]를 원소를 제거한다.

 

위의 방법을 반복하여 모든 연산자를 이용해서 계산을 수행하면 numList에 하나의 숫자가 남게 된다.

(해당 숫자가 이번 연산자 우선순위를 이용한 상금이다.)

 

이렇게 계산한 상금 중 가장 큰 값을 반환하면 된다.

 

---

전체 코드

 

from itertools import permutations
import re

def calculation(n1, n2, op):
    if op == "+":
        return n1+n2
    elif op == "-":
        return n1-n2
    else:
        return n1*n2
    
def solution(expression):
    answer = 0
    
    operators = set(re.findall("[^0-9]+", expression))
    
    for priority in list(permutations(operators, len(operators))):
        numList = list(map(int, re.findall("[0-9]+", expression)))
        opList = re.findall("[^0-9]+", expression)
        
        for target_op in priority:
            
            while target_op in opList:
                idx = opList.index(target_op)
                res = calculation(numList[idx], numList[idx+1], target_op)
                
                numList[idx] = res
                numList.pop(idx+1)
                opList.pop(idx)
        
        candidate = abs(numList[0])
        
        if candidate > answer:
            answer = candidate
                    
    return answer

 

---

느낀 점

 

1. index out of range에 주의하라

 

처음 문제를 풀 때 연산을 수행한 후 사용된 연산자와 숫자를 제거하는 단계에 for 문을 이용했다.

for 문 내부에서 리스트의 원소를 제거하기 때문에 해당 에러가 발생했다.

⇒ 반복문 내부에서 리스트의 원소를 삽입, 제거하는 경우 while문이 더 적합할 거 같다.

 

2. eval() 함수 사용

 

다른 사람 풀이를 통해 eval()이란 함수의 존재를 알게 되었다.

 

eval()는 매개변수로 주어진 식을 그대로 계산하여 결괏값을 반환해 주는 함수이다.

즉 eval("1+2")의 반환 값은 3이다.

만약 다음에 문자열 형태의 식이 주어지는 문제를 만난다면 한번 사용을 고려해봐야겠다.