수식 최대화 풀이
이 문제는 제가푼 코드보다 시골우유 , 신철호 님께서 푼 코드가 훨씬 간결하고 세련되어서 그 코드를 바탕으로 풀이를 해보겠습니다.
시골우유, 신철호 님의 코드
import re
from itertools import permutations
def solution(expression):
#1
op = [x for x in ['*','+','-'] if x in expression]
op = [list(y) for y in permutations(op)]
ex = re.split(r'(\D)',expression)
#2
a = []
for x in op:
_ex = ex[:]
for y in x:
while y in _ex:
tmp = _ex.index(y)
_ex[tmp-1] = str(eval(_ex[tmp-1]+_ex[tmp]+_ex[tmp+1]))
_ex = _ex[:tmp]+_ex[tmp+2:]
a.append(_ex[-1])
#3
return max(abs(int(x)) for x in a)
내 코드
import itertools
import re
import copy
#expression = "100-200*300-500+20"
def split_num(sepr_list, expression):
regular_exp = '|'.join(map(re.escape, sepr_list))
return re.split(regular_exp, expression)
def split_sign(sepr_list, expression) :
result = []
for i in expression :
if i in sepr_list : result.append(i)
return result
def solution(expression):
answer = []
sepr_list = '*', '+', '-'
nums = split_num(sepr_list, expression)
signs = split_sign(sepr_list, expression)
sign_kinds = set(signs)
if(len(sign_kinds) == 1) : return abs(eval(expression))
permu = list(itertools.permutations(sign_kinds, len(sign_kinds)))
for i in permu : #conbinations
nums_ = copy.deepcopy(nums)
signs_ = copy.deepcopy(signs)
for j in i : #sign
while(j in signs_) :
ind = signs_.index(j)
signs_.pop(ind)
nums_[ind] = str(eval(nums_[ind] + j + nums_[ind+1]))
nums_.pop(ind+1)
answer.append(abs(eval(nums_[0])))
return max(answer)
우선 이 문제를 풀기위해 2가지 사전 잡기술(?)이 필요합니다.
- 리스트 내포 for문
- 정규식
리스트 내포 for문은 코드의 간결성을 위한 기술입니다. 간단한 예시를 보여드리면
numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
result = []
for i in numbers :
if i %2 == 0 :
result.append(i)
print(result)
결과 : [2, 4, 6, 8, 10]
리스트 내포 for문
numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
retult = [x for x in numbers if x%2 == 0]
print(result)
결과 : [2, 4, 6, 8, 10]
같은 일을 하는 코드지만 내포를 사용하면 더욱더 간결한 코드를 만들 수 있습니다.
자바를 혼자 독학할 때 정규식에관한 설명을 본적이 있는데, 2학년때 오토마타의 악몽이 떠오르며 대충보고 넘겼었던걸 정말 후회됩니다. 뭔가 복잡하고 이상한 특수문자들이 많아 보기 눈이 아프겠지만, 보면 볼수록 규칙이있는 공식인 느낌을 받았습니다.
정규식은 여기서 다루기엔 너무 양이 많고 쓸데없으니 여기서 설명은 하지 않겠지만, 꼭 공부하시길 바랍니다.
해설
이 문제는 str타입의 다항식의 항을 하나씩 계산 해나가며 최신화를 시켜야한다는 점이 조금 어려웠습니다.
이 문제의 핵심은
- 연산자들 permutation
- 숫자와 연산의 분리
- 항 하나를 계산하고 최신화
이렇습니다.
연산자 순열 permutation
우선 expression = "100-200*300-500+20" 에서 연산자만 떼옵시다.
op = [x for x in ['*','+','-'] if x in expression]
이렇게 되면 ['*', '+', '-']만 op에 저장됩니다.
그리고 op를 permutation 시켜주면 되는데 for문이 iterable이 가능한 객체에대해서 동작한다는 것을 이용하여 아주 간결하게 코딩을 하셨습니다(한수 배웠습니다).
op = [list(y) for y in permutations(op)]
이렇게되면 op에는 [['*', '+', '-'], ['*', '-', '+'], ...] 총 24개(n!)의 연산 순서 후보들이 저장되게 됩니다.
숫자와 연산자 분리
파이썬에서 정규식을 사용하게 해주는re 모듈의 split을 이용하여 expression을 숫자, 연산자로 분리해줍니다.
import re
ex = re.split(r'(\D)',expression)
여기서 r'(\D)' 정규식을 해석해 보면
r: 정규식을 활용할 객체가 순수문자임을 암시함.(express안에\,^등등 re모듈의 예약어가 없다라는 뜻)
\d: 숫자인것을 찾는다
\D: 숫자가 아닌것을 찾는다
(): 추출할 패턴을 지정한다.
사실 r은 없어도 되지만, 테스트케이스에 어떤것이 나올지 모르니 넣은 것 같고, 숫자가 아닌 것들을 기준으로 split 하겠다라는 뜻이다.
그렇게 되면 ex 에 ['100', '-', '200', '*', '300', '-', '500', '+', '20']가 저장된다.
계산
op : [['*', '+', '-'], ['*', '-', '+'], ...]
ex :['100', '-', '200', '*', '300', '-', '500', '+', '20']
op에서 연산자 순열을 하나씩 꺼내고, 꺼낸 순열에서 연산자를 꺼내 ex를 계산해주고 각 계산값들을 리스트에 저장해준다.
for x in op: # 순열 하나를 꺼냄 ex) ['+', '-', '*']
_ex = ex[:] # ex복사본, 복사본 안해주고 원본에다 하면 원본이 바뀜.
for y in x: # x에서 연산자 하나씩 꺼냄
#계산하는 파트
while y in _ex: # 복사본안에 꺼낸 연산자가 없을 때 까지 반복해서 계산
tmp = _ex.index(y)
_ex[tmp-1] = str(eval(_ex[tmp-1]+_ex[tmp]+_ex[tmp+1]))
_ex = _ex[:tmp]+_ex[tmp+2:]
a.append(_ex[-1]) #계산 결과값을 모아둔 list
계산하는 파트를 좀더 이해하기 쉽게 시각적으로 보면
이런식으로 계산이 된다.
코드
import re
from itertools import permutations
expression = "100-200*300-500+20"
def solution(expression):
#1
op = [x for x in ['*','+','-'] if x in expression]
op = [list(y) for y in permutations(op)]
ex = re.split('(\D)',expression)
#2
a = []
for x in op:
_ex = ex[:]
for y in x:
while y in _ex:
tmp = _ex.index(y)
_ex[tmp-1] = str(eval(_ex[tmp-1]+_ex[tmp]+_ex[tmp+1]))
_ex = _ex[:tmp]+_ex[tmp+2:]
a.append(_ex[-1])
#3
return max(abs(int(x)) for x in a)