풀리자마자 기뻐서 올리기 때문에 코드 안 깔끔함 주의, 최적화 안 되어 있음 주의
문제
문제가 너무 길다.. 요약하자면 수식이 문자열로 주어지는데, 여기서 연산자들(-,*,+ 만 주어짐)의 모든 가능한 우선순위를 따져봤을 때 수식의 답이 가장 커지는 경우의 값을 찾는 것이다. 단, 결과값은 절대값으로 따진다. 기타 조건은 문제 참조 ㅎㅎ
어떻게 풀었지?
요새 완전탐색만 주구장창 풀어서 그런지 보자마자 완전탐색일 거라고 생각했다. 문자열을 받았을 때 연산자들만 골라내서, permutation으로 순열을 만들어낸 다음 이 순열의 순서에 따라 우선순위를 두어서 전부 계산하는 방식으로 접근해야겠다고 생각했다. 우선순위는 약간 스택 계산기처럼 써야겠다고 생각했다.
어디서 헤맸지?
-
일단 가장 어의없는 부분, 아무 생각없이 입력값인 expression에서 한칸씩 가면서 생각했는데 생각해보니까 숫자가 꼭 한자리가 아니더라 ㅋㅋㅋㅋㅋㅋㅋㅋ 내 자신이 정말 멍청하다고 생각했다. 시간 맞춰서 풀려다 보니까 빈 문자열을 두고 추가추가 하다가 연산자를 만나면 스택에 푸시했었는데, 출력값이 이상했다. 당연하게도 연산자를 안만나는 마지막 값은 스택에 푸시가 안됐겠지!!!!!!!!!!!!!!!!! 그래서 정규표현식은 생각이 안나가지고, "+' 를 " + ", "-"를 " - " 이런 식으로 빈칸을 양옆에 추가한 다음에 split(" ")해서 배열에 넣어서 하나씩 가져왔다😢. 다른 친구가 푼 걸 보니까 re 잘 쓰던데.. 나도 데이터 공부하다가 re 잘 써야지 했는데..
-
그리고 스택 계산기를 너무 오랜만에 하다보니까 약간 헷갈렸다. 그냥 나보다 우선순위가 높은 애가 스택에 있으면 빼가지고 계산 시키고 내가 들어가는 방식. 근데 이건 출력값 보면서 어케어케 해결.
Code
from itertools import permutations
max_val = float("-inf")
def operation(op,num1,num2) :
if op == "+" :
return num1+num2
elif op == "-" :
return num1-num2
elif op == "*" :
return num1*num2
def cal(op,expression) :
global max_val
expression = expression.replace("+"," + ").replace("-"," - ").replace("*"," * ").split(" ")
#이 부분을 정규표현식을 써서 더 잘 처리할 수 있을 것 같다.
val = 0
op_index = [0+i for i in range(len(op))]
op_index = sorted(op_index, reverse=True)
op_compare = dict(zip(op,op_index))
#급해가지고 이렇게 썼었는데 더 잘 쓰는 법이 있지 않을까
stack_op = []
stack_num = []
for s in expression :
if s in op :
if not stack_op :
stack_op.append(s)
else :
stack_op_top = stack_op[-1]
if op_compare[s] > op_compare[stack_op_top] :
stack_op.append(s)
else :
while stack_op and op_compare[s] <= op_compare[stack_op[-1]] :
stack_op_top = stack_op.pop()
num1 = stack_num.pop()
num2 = stack_num.pop()
result = operation(stack_op_top,num2,num1)
stack_num.append(result)
stack_op.append(s)
else :
stack_num.append(int(s))
#남은 부분 처리
while stack_op :
top = stack_op.pop()
num1 = stack_num.pop()
num2 = stack_num.pop()
result = operation(top,num2,num1)
stack_num.append(result)
m = stack_num[0]
max_val = max(abs(m),max_val)
def solution(expression):
answer = 0
operation = []
for c in expression :
if c == "+" or c == "-" or c == "*" :
if c not in operation :
operation.append(c)
operation_subset = list(permutations(operation))
for op in operation_subset :
cal(op,expression)
answer = max_val
return answer
뭔가 코드를 항상 최적화 안하고 올리니까 발전이 없는 것 같기도 하고.. 물론 다시 보기는 하지만 귀찮아서 포스팅 수정은 안하는데.. 이제 좀 다듬어서 올려야 할 것 같다. 🤔
