Level 2 수식 최대화 <2020 카카오 인턴십> Python 3

https://programmers.co.kr/learn/courses/30/lessons/67257?language=python3 

코딩테스트 연습 - 수식 최대화

 

최종 코드

• GitHub -> https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level2_수식최대화.py

GitHub - hwayeon351/Programmers-Algorithms: 프로그래머스 알고리즘 소스 코드 모음

from itertools import permutations
from collections import deque
def solution(expression):
    answer = 0
    #1. 연산자와 피연산자 split
    nums = []
    op = []
    ori_operation = []
    num = ""
    n = 0
    for e in expression:
        if e.isdigit():
            num += e
        else:
            n = int(num)
            nums.append(n)
            ori_operation.append(n)
            num = ""
            op.append(e)
            ori_operation.append(e)
    n = int(num)
    nums.append(n)
    ori_operation.append(n)
    
    #2. 연산자 우선순위 조합 구하기
    op_kinds = list(set(op))
    op_permu = permutations(op_kinds, len(op_kinds))
    
    #3. 계산하기
    op_stack = []
    operation_stack = []
    for per in op_permu:
        operation = deque(ori_operation[:])
        operation_stack = []
        op_stack = list(per)
        while True:
            if len(operation) == 0:
                if len(operation_stack) == 1:
                    result = abs(operation_stack[-1])
                    if result > answer: answer = result
                    break
                operation = deque(operation_stack)
                operation_stack = []
                op_stack.pop()
            k = operation.popleft()
            if str(k).isdigit():
                operation_stack.append(k)
            elif k == op_stack[-1]:
                n1 = operation_stack.pop()
                n2 = operation.popleft()
                if k == '+':
                    n3 = n1+n2
                elif k == '-':
                    n3 = n1-n2
                elif k == '*':
                    n3 = n1*n2
                operation_stack.append(n3)
            else: operation_stack.append(k)

    return answer

---

풀이 과정

풀이 시간 1시간 6분

from itertools import permutations
from collections import deque
def solution(expression):
    answer = 0
    
    #1. 연산자와 피연산자 split -> O(len(expression)) = O(n)
    #nums = 피연산자들을 담은 리스트, op = 연산자들을 담은 리스트, ori_operation = expression의 연산자와 피연산자들을 순서대로 담은 리스트
    nums = []
    op = []
    ori_operation = []
    num = ""
    n = 0
    for e in expression:
    	#현재 문자열 e가 숫자인 경우, 문자열 num에 이어 붙인다
        if e.isdigit():
            num += e
        #현재 문자열 e가 문자인 경우(연산자인 경우를 의미)
        else:
        	#이전에 받아온 피연산자를 담은 문자열 num을 int형으로 변환 후, nums 리스트와 ori_operation에 담는다
            n = int(num)
            nums.append(n)
            ori_operation.append(n)
            
            #다음 피연산자를 받아오기 위해 num을 ""로 초기화
            num = ""
            
            #피연산자 e를 리스트 op과 ori_operatio에 담는다
            op.append(e)
            ori_operation.append(e)
            
    #마지막 피연산자를 nums와 ori_operation 리스트에 담는다
    n = int(num)
    nums.append(n)
    ori_operation.append(n)
    
    
    #2. 연산자 우선순위 조합 구하기 - O(len(op_kinds)!) = O(1) => 이 때, 연산자 종류는 최대 +, -, * 3 종류이므로 3! = 6, 즉, 상수의 시간복잡도를 가진다.
    op_kinds = list(set(op))
    op_permu = permutations(op_kinds, len(op_kinds))
    
    #3. 계산하기
    #연산자 우선 순위를 담는 리스트 op_stack
    op_stack = []
    #연산이 이뤄지는 과정을 구현하기 위한 operation_stack
    operation_stack = []
    
    #각 연산자 우선순위 경우에 따라 수식을 계산한다 -> O(6*len(ori_operation)*3) = O(n)
    for per in op_permu:
    	#연산자와 피연산자들을 연산 순서대로 담는 리스트 operation
        operation = deque(ori_operation[:])
        operation_stack = []
        op_stack = list(per)
        
        while True:
 			#최우선 연산자인 op_stack[-1]에 대해서 연산이 모두 이뤄진 경우,
            if len(operation) == 0:
            	#가장 작은 우선 순위 연산자까지 연산이 모두 이뤄진 경우, 해당 연산자 우선순위 경우의 수에 대해 연산이 모두 이뤄짐을 의미
                if len(operation_stack) == 1:
                	#결과 값이 operation_stack의 top에 담겨있다
                    result = abs(operation_stack[-1])
                    #answer값과 비교하여 answer값 갱신
                    if result > answer: answer = result
                    break
                    
                #operation_stack이 2개 이상인 경우, 다음 연산자 우선순위에 대해 연산을 이어간다
                #이전 연산이 이뤄진 후 연산 수식은 operation_stack에 담겨있으므로 operation을 operation_stack에 담아주고, operation_stack은 비워준다
                operation = deque(operation_stack)
                operation_stack = []
                
                #op_stack.pop()을 통해 다음 우선순위의 연산자를 top으로 한다.
                op_stack.pop()
                
            #수식의 피연산자 또는 연산자를 k에 담는다
            k = operation.popleft()
            
            #k가 피연산자인 경우, operation_stack에 Push
            if str(k).isdigit():
                operation_stack.append(k)
                
            #k가 연산자인 경우, 현재 우선 순위의 연산자와 같으면 연산을 한다
            elif k == op_stack[-1]:
            	#피연산자는 operation_stack의 top에 있는 숫자 n1과 operation의 front에 있는 숫자 n2이다
                n1 = operation_stack.pop()
                n2 = operation.popleft()
                if k == '+':
                    n3 = n1+n2
                elif k == '-':
                    n3 = n1-n2
                elif k == '*':
                    n3 = n1*n2
                #연산 결과를 operation_stack에 담아준다
                operation_stack.append(n3)
                
            #k가 연산자이면서 현재 우선 순위의 연산자가 아니라면 다음 차례에 연산을 수행하기 위해 operation_stack에 담아준다
            else: operation_stack.append(k)

    return answer
#시간복잡도 = O(n), 공간복잡도 = O(n)

 

다른 풀이

import itertools
import copy

def get_num(per_op, n_list):
    for op in per_op:
        while(op in n_list):
            i = n_list.index(op)
            if n_list[i] == op:
                result = 0
                n1 = n_list[i-1]
                n2 = n_list.pop(i+1)
                if op == '+':
                    result = n1+n2
                elif op == '-':
                    result = n1-n2
                elif op == '*':
                    result = n1*n2
                n_list[i-1] = result
                del(n_list[i])                
    return abs(n_list[0])

def solution(expression):
    op = ["*","+","-"]
    num_list = []
    result = []
    per_op = list(map(''.join, itertools.permutations(op)));
    num_str = ""
    for i in expression:
        if i in op:
            num_list.append(int(num_str))
            num_str = ""
            num_list.append(i)            
        else: num_str += str(i)
    num_list.append(int(num_str))

    for s in per_op:
        result.append(get_num(s, copy.deepcopy(num_list)))
    return max(result)

---

참고

• 1. 키패드 누르기 ->2021.08.24 - [코테 노트/프로그래머스] - Level 1 키패드 누르기 <2020 카카오 인턴십> Python 3 

Level 1 키패드 누르기 <2020 카카오 인턴십> Python 3

• 3. 보석 쇼핑 -> https://hwayomingdlog.tistory.com/136

Level 3 보석 쇼핑 <2020 카카오 인턴십> Python 3

• 4. 경주로 건설 -> 2021.09.01 - [코테 노트/프로그래머스] - Level 3 경주로 건설 Python 3

Level 3 경주로 건설 Python 3

• 5. 동굴 탐험 ->