[Programmers]2020 카카오 인턴십: 수식 최대화/문자열(Python)

programmers.co.kr/learn/courses/30/lessons/67257

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

이전에 풀었었던 수식 최대화 문제를 최근에 스터디 때문에 다시 풀게 되었다

미팅 때 너무너무 좋은 라이브러리를 알게 돼서 다시 풀어봤는데 풀이가 엄청나게 간소화되어서 다시 올린다

 

코딩테스트에서 사용하기 좋은 python 메소드인, permutations combinations eval이 존재한다.

이 중 permutations와 combinatiosn는 각각 from itertools import permutations / combinations를 선언해서 사용하면 되고 eval은 import가 필요 없다.

 

1️⃣ permutations( list, k ) : list 내에 있는 element를 k개 뽑은 순열을 리턴한다. list로 형변환하여 넣어줄 수 있다.

ex)

list = [1,2,3]

list(permutation(list, 2)) == [(1,2), (1,3), (2,1), (2,3), (3,1), (3,2)]

2️⃣ combinations( list, k ) : list 내에 있는 element를 k개 뽑은 조합을 리턴한다. 마찬가지.

ex)

list = [1,2,3]

list(combinations(list, 2)) == [(1,2), (1,3), (2,3)]

3️⃣ eval( str ) : str 내에 있는 수식을 계산한 값을 리턴한다.

ex) eval(500+2*3) == "506"

 

위의 함수들을 이용해서 연산자의 우선순위 순열을 구해주고, 문자열로 된 수식을 슬라이싱해서 계산해주는 시뮬레이션 문제였다.

import copy
from itertools import permutations

def calculation(p, operator, num, expression):
    for op in p:    #p에 들은 연산자 우선순위에 의해
        i=0
        for _ in range(len(operator)):  #수식의 연산자 개수만큼 반복
            if operator[i]==op:     #현재 먼저 계산해야 하는 연산자(우선순위)에 맞게 계산 진행
                st=str(num[i])+operator[i]+str(num[i+1])
                num[i]=eval(st)			#해당 수식 계산 후 num[i]에 대입
                num.pop(i+1)        #계산 진행 후 연산자와 피연산자 하나씩 줄기 때문에 각각 그 위치에 있는 것들 pop
                operator.pop(i)
            else: i+=1      #계산이 일어나야 개수가 하나씩 줄고, 아니면 안 줄기 때문에 index 증가
    return num[0]       #결국 마지막 남은 숫자가 답이 됨

def solution(expression):
    num=[]      #숫자를 잘라서 저장할 리스트
    op=[]       #연산자를 저장할 리스트
    e=0
    for i in range(len(expression)):
        if not expression[i].isdigit():     #연산자라면
            num.append(int(expression[e:i]))        #이전에 나온 숫자를 int로 변환해서 리스트에 삽입
            op.append(expression[i])                #연산자도 삽입
            e=i+1
    num.append(int(expression[e:]))     #마지막 숫자도 안 들어갔으니 삽입
    operator=list(set(op))              #중복 제거
    operator.sort()                 #permutation
    
    perm=list(permutations(operator, len(operator)))	#가능한 연산자의 순열 구하기
    
    ans=0
    for c in perm:
        N=copy.deepcopy(num)        
        O=copy.deepcopy(op)
        result = calculation(c, O, N, expression)
        if result<0:result*=-1        #절대값 처리
        if result>ans:ans=result          #최대값 갱신

    return ans