오늘 푼 문제는 카카오 인턴십 문제인 수식 최대화입니다.
레벨 2라 방심했는데 카카오 문제답게 그렇게 쉽지는 않았습니다.
역시나 문자열 처리가 능숙해야 편하게 푸는 문제였고 정규표현식 등의 필요성을 한번 더 느꼈습니다.
문제는 간단히 주어진 수식에서 -, *, + 연산자들의 우선순위가 바뀌었을 때 최대 절댓값을 가지는 수식을 구하는 문제입니다.
저번에 했던 불량 사용자처럼, 경우의 수를 모두 구해놓고 DFS를 하는 것처럼 반복하면 될 거라 생각했습니다.
근데 여기서 제가 느끼기에 부족했던 테크닉은 다음과 같습니다.
- Itertool을 이용한 Permutation(순열) 생성 -> 몰라서 직접 다 타이핑하여 배열 만듬
- 마지막으로 계산할 때 뭔가 최적화를 못한 느낌?
- 숫자와 연산자 분리 과정도 조금 복잡하게 짠 것 같다.
아무튼 단계별로 풀어보겠습니다. 우선 수식에서 숫자와 연산자를 분리하기로 했습니다.
그냥 무작정 수식을 한 번 순회하면서 숫자가 나오면 저장하고 있다가 연산자가 나오면 분리하는 식으로 접근합니다.
# 연산자와 숫자를 분리하는 과정
buffer = ''
nums = []
operands = []
for char in expression:
if char.isdigit():
buffer += char
else:
nums.append(int(buffer))
operands.append(char)
buffer = ''
nums.append(int(buffer))그 다음, 연산자들의 우선순위를 미리 정해놓기 위해 만들었습니다.
# 연산자 간 순열 만들기
com = [['*', '-', '+'], ['+', '*', '-'],
['*', '+', '-'], ['+', '-', '*'],
['-', '*', '+'], ['-','+','*']]참고로 itertool을 쓰면 매우 편하게 만들 수 있습니다.
from itertools import permutations
com = [list(x) for x in permutations(['+', '-', '*'], 3)]다음으로 총 6개의 우선순위가 나왔으니 순서대로 넣어가면서 수식 값을 조사해야 합니다.
이 부분을 구현하는 데 정말 오래 걸렸고 단순무식하게 구현해보았습니다.
def calc(nums, operands, com):
# 연산자 배열 원본이 변하지 않도록 복사
new_operands = deepcopy(operands)
# 연산자가 모두 없을 때까지 반복
while new_operands:
# 우선 순위 배열에서 연산자 하나를 꺼냄
priority = com.pop()
# 연산자 배열에 해당 우선순위의 연산자가 있을 떄까지 반복
while priority in new_operands:
# 연산자 배열을 순차적으로 돌면서 우선순위와 일치하면 계산 실행
for i, op in enumerate(new_operands):
if op == priority:
number = eval(str(nums[i])+op+str(nums[i+1]))
if i < len(nums)-2:
nums = nums[:i]+[number]+nums[i+2:]
else:
nums = nums[:i]+[number]
new_operands.pop(i)
# 숫자 배열 업데이트를 위해 하나만 계산하고 다시 빠져나감
break
return abs(nums[0])우선 순위 별로 하나씩 calc 함수에 넣어주면서 계산합니다.
우선순위 배열의 연산자를 하나씩 꺼내면서 해당 연산자가 있는 위치에서 숫자를 더하고 숫자가 담긴 배열을 업데이트합니다. 이를 반복하면서 연산자가 모두 사라질 때까지 반복하여 최종 결괏값을 return합니다. 이 중 최댓값을 return 하면 문제는 풀리게 됩니다.
다만 코드가 이해하기 힘들고 너무 많은 반복이 있어 더 깔끔하게 푸는 방법이 있지 않을까 합니다.
레벨 2에서도 헤매다니 카카오 문제가 어려운건지, 알고리즘을 너무 놓은건지 약간 반성이 됩니다.
전체 코드는 다음과 같습니다.
import collections
from copy import deepcopy
def solution(expression):
answer = 0
# 연산자와 숫자를 분리하는 과정
buffer = ''
nums = []
operands = []
for char in expression:
if char.isdigit():
buffer += char
else:
nums.append(int(buffer))
operands.append(char)
buffer = ''
nums.append(int(buffer))
# 연산자 간 순열 만들기
com = [['*', '-', '+'], ['+', '*', '-'],
['*', '+', '-'], ['+', '-', '*'],
['-', '*', '+'], ['-','+','*']]
# 우선 순위를 하나씩 넣어가며 수식 값 계산
for i in range(len(com)):
answer = max(answer, calc(nums, operands, com[i]))
return answer
def calc(nums, operands, com):
# 연산자 배열 원본이 변하지 않도록 복사
new_operands = deepcopy(operands)
# 연산자가 모두 없을 때까지 반복
while new_operands:
# 우선 순위 배열에서 연산자 하나를 꺼냄
priority = com.pop()
# 연산자 배열에 해당 우선순위의 연산자가 있을 떄까지 반복
while priority in new_operands:
# 연산자 배열을 순차적으로 돌면서 우선순위와 일치하면 계산 실행
for i, op in enumerate(new_operands):
if op == priority:
number = eval(str(nums[i])+op+str(nums[i+1]))
if i < len(nums)-2:
nums = nums[:i]+[number]+nums[i+2:]
else:
nums = nums[:i]+[number]
new_operands.pop(i)
# 숫자 배열 업데이트를 위해 하나만 계산하고 다시 빠져나감
break
return abs(nums[0])
시간 복잡도 : O(S+n) ? S: 문자열의 길이, n : 연산자의 개수
이유 : 먼저 문자열을 모두 탐색하여 연산자와 숫자를 분리했고, 마지막으로 계산할 때 결국 연산자의 개수만큼 계산이 수행되기 때문에 이렇게 생각
