https://programmers.co.kr/learn/courses/30/lessons/67257
프로그래머스 2단계 정도의 문제이다.(생각보다 난이도가 낮구나...)
코드 먼저 살펴보자!
from itertools import permutations
import re
def calculate(op, num1, num2) :
result = 0
if op == '*' :
result = int(num1) * int(num2)
if op == '+' :
result = int(num1) + int(num2)
if op == '-' :
result = int(num1) - int(num2)
return result
def solution(expression) :
temp = []
result = []
last_index = 0
has = set()
# re.split('(\D)', expression) 숫자가 아닌것을 기준으로 split 한다, \d면 숫자겠지???
for i in range(len(expression)) :
if expression[i] in ['*', '+', '-'] :
temp.append(expression[last_index:i])
temp.append(expression[i])
has.add(expression[i])
last_index = i + 1
if last_index != len(expression) :
temp.append(expression[last_index:])
last_index = 0
priority_list = list(map(list,permutations([*has], len([*has]))))
for priority in priority_list :
l = list(temp)
for op in priority :
stack = []
while (len(l) != 0) :
tmp = l.pop(0)
if tmp == op :
stack.append(calculate(op, stack.pop(), l.pop(0)))
else :
stack.append(tmp)
l = stack
result.append(abs(l.pop(0)))
return max(result)
print(solution("100-200*300-500+20"))
print(solution("50*6-3*2"))
접근 방법
* 우선순위를 나열해줄 순열 코드가 필요할것 같았다(permutations(배열, 길이))
* 전위, 중위, 후위 표현식을 구현할때 사용하는 stack을 사용해야겠다고 생각이 들었다.
막혔던 부분
* 우선순위가 정해진 숫자 기호별로 접근을 할때 값을 다시 가져오고 계산하는 부분에서 애를 먹었다.
* 입력받은 표현식을 숫자, 연산기호 별로 나누는데 애를 좀 먹었었다.(re 내장 라이브러리를 나중에 알았다)
처음 접했을때는 굉장히 난감 했는데 지하철에서 코딩하면서 접근 방법을 떠올렸던 문제였다.
보석 쇼핑에 비해서는 쉬웠던것 같다.
'알고리즘' 카테고리의 다른 글
기둥과 보 설치[2020 KAKAO BlIND RECRUITMENT] (0) | 2021.11.14 |
---|---|
나 잡아 봐라[2019 LINE 인턴채용] (0) | 2021.11.14 |
보석 쇼핑[2020 카카오 인턴십] (0) | 2021.11.14 |
책 페이지(백준 1019) (0) | 2021.10.25 |
조합 0의 개수 (0) | 2021.10.24 |