전에 눌렀다가 후위 표기식 변환하고 계산해야하는 문제인건 알겠는데 내가 후위 표기식 변환하는걸 잊어버렸네.. 게다가 연산자 우선순위도 알아서 바꿔야된다고...? 어케 풀어 하고 살포시 뒤로 가기를 눌렀었던 문제인데, 이번에는... 집념으로... 풀었다!
크게 2가지 단계로 나눠서 생각할 수 있었다.
- 연산자 우선 순위 설정
- 순서배열이네~!
- 연산자 우선 순위대로 계산해서 절댓값이 최대인 것 구하기.
- 후위 표기식으로 변환
- 후위 표기식 계산
나는 2번을 더 먼저 해야한다고 생각해서 (이미 알고 있었으니까) 2번을 먼저 구현했다.
여기서 헤맨 부분은 연산자 우선 순위를 어떻게 계산할 것인가 였는데,
- 연산자 순위가 높은 것 부터
"*+-"이런식으로 받아서 for 문으로 쪼개..?
- 앗..? 그냥 index 를 반환하자!!
- 그럼 그냥 index 작으면 우선 순위(사실 상 여기에선 순위라기 보단 가중치 값이 클수록 우선순위가 높다고 뒀으니까.)도 작게 하자.
"-+*"이렇게 우선 가중치 오름차순으로 넘겨주기로 결정했다.
1. 후위 표기식 변환
from itertools import permutations
import re
# expression : 중위표기식으로 이루어진 배열(원소가 숫자, 연산자)
# order : 표기식에 등장하는 연산자를 우선순위가 낮은 것부터 "-+*" 형식으로 배열한 문자열
# 을 넣으면, 후위표기식 배열로 바꾸어서 return 해주는 함수.
def suffix(expression, order):
# 연산자 우선순위를 return 해주는 녀석.
# 함수 밖에서 선언하면 order 를 따로 전해줘야해서 함수 안에 정의했다!
def priority(op):
return order.index(op)
res = []
stack_op = []
# re 정규식 모듈에서 findall, sub 은 이제 잘 쓴다!
elements = re.findall("[0-9]+|[\+\-\*]", expression)
# 후위표기식 알고리즘
for e in elements:
# 숫자이면 식에 바로 쓰고,
if e.isdigit():
res.append(e)
# 연산자이면
elif e == "+" or e == "-" or e == "*":
# 새로 들어오는 것의 우선순위가 높으면 연산자 스택에 넣고,
if stack_op and priority(stack_op[-1]) < priority(e):
stack_op.append(e)
# 낮으면 우선순위가 자기보다 낮은 것이 나올때까지 팝해서 식에 쓴다.
else:
while stack_op and priority(stack_op[-1]) >= priority(e):
res.append(stack_op.pop())
stack_op.append(e)
# 연산자 스택에 뭔가 남아있다면 꺼내서 식에 쓰기.
while stack_op:
res.append(stack_op.pop())
return res알고리즘은 스택 공부할 때 (약 두달 전) 해놨어서 어렵진 않았고, 대신 항상 문제인 부분이, 스택에서 팝하는 모든 코드 전에 스택이 비었는지 꼭 확인 해야한다는 것!
2. 후위 표기식 계산
def calculateSuffix(suffixArr):
stack_num = []
for e in suffixArr:
# 숫자이면 스택에 넣고
if e.isdigit():
stack_num.append(int(e))
# 연산자이면
else:
if stack_num: # 숫자 스택이 비어있지 않을 때,
# 두개씩 꺼내서 연산 하고 다시 스택에 넣는다.
# 후위표기식 특성 상 안 비어 있으면 두개일 수 밖에 없음
second = stack_num.pop()
first = stack_num.pop()
if e == "+":
stack_num.append(first + second)
elif e == "-":
stack_num.append(first - second)
elif e == "*":
stack_num.append(first * second)
# 마지막에 스택에 들어가 있는 것이 계산 결과 값
return stack_num[0]계산도 스택이 비어있는지 확인 하는 부분 없어서 오류났었다.
3. 연산자 우선순위 설정 - 조합
def solution(expression):
answer = 0
ops = re.findall("[\+\-\*]", expression)
ops = list(set(ops))
orders = list(permutations(ops, len(ops)))
for o in orders:
order = "".join(o)
res = calculateSuffix(suffix(expression, order))
res = -res if res < 0 else res
if answer < res:
answer = res
return answer서치해서 푼 부분 - from itertools import permutations, orders = list(permutations(ops, len(ops)))
후위표기식 부분 끝나면 끝인줄 알았는데, 이 부분도 꽤나 속을 썩였다...
3개를 배열하는 거니까 3! 인거 알겠는데... 각각 경우를 컴퓨터로 어떻게 구하게 하냐고... for 문 3개 중첩해서 중복되는거 없게할까 했는데...
지금이야 연산자가 3개지만 나중에 5개짜리 문제가 나오면 어쩔겨.. 이런 생각이 들어서 직접 구현을 하려다가, 이거 2단계인데 실전에서 이런 문제 더 붙잡고 있으면 뒷 문제는 못푼다. 생각이 들어서 그냥 빠르게 검색을 했다.
다행히도 아주 좋은 from itertools import permutations / combinations,
list(permutations(배열, 조합에서 뽑을 원소 개수)) 라이브러리가 있어서 빠르게 해결할 수 있었다. 그러나 순열 조합도 직접 한번 구현해보는 것이 좋을듯!!
참고
