[프로그래머스(파이썬/Python)] 수식 최대화(2020 카카오 블라인드 채용)

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

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

 

2020년 카카오 블라인드 채용에 있는 문제로, 문제의 요구사항을 충실히 구현하면 되는 문제입니다.

 

우선 문자열로 주어진 expression을 splitExpression() 함수를 구현해서 숫자와 연산자 집합으로 분리를 했습니다.

 

문제 조건에서

• "-56+100"처럼 피연산자가 음수인 수식도 입력으로 주어지지 않습니다.

라는 내용이 있기 때문에, numbers 배열의 길이는 operations 배열 길이보다 항상 1이 작고 operation에 존재하는 연산자의 인덱스를 통해 그 양옆에 존재하는 숫자에 접근할 수 있습니다.

 

따라서, 다음으로는 +, -, * 세 가지의 연산자 우선순위의 순열에 대해 완전탐색을 해주면 됩니다.

 

1) 파이썬의 permutation을 이용하여 가능한 6가지의 순열을 찾아내고, 2) 첫번째 우선순위를 갖는 연산자부터 operation을 탐색하여 해당 operation이 위치하는 인덱스를 찾고, 3) 그 인덱스를 통해 numbers 배열에서 양 옆의 숫자를 찾아 값을 갱신해주면 됩니다.

 

[풀이]

from itertools import permutations as P

def splitExpression(expression, sep):
    numbers, operations, integer = [], [], ""
    for s in expression:
        if s in sep:
            numbers.append(int(integer))
            operations.append(s)
            integer = ""
        else:
            integer += s
    numbers.append(int(integer))

    return numbers, operations

def solution(expression):
    # 연산자 종류
    sep = ['*', '+', '-']
    
    # 주어진 expression을 숫자와 연산자로 구분해서 저장할 리스트
    numbers, operations = splitExpression(expression, sep)

    answer = 0
    # 가능한 모든 조합에 대해 우승 상금을 정해본다.
    for priority_ops in list(P(sep, 3)):
        temp_num, temp_op = numbers[:], operations[:]

        # 연산자 우선순위의 순열을 각각 조회
        for op in priority_ops:
            # 우선순위를 갖는 연산자부터 전부 연산을 수행해본 후 결과값 저장
            while True:
                try:
                    opIndex = temp_op.index(op)
                    temp_op.pop(opIndex)
                    left = temp_num.pop(opIndex)
                    right = temp_num.pop(opIndex)

                    if op == "+":
                        temp_num.insert(opIndex, left + right)
                    elif op == "-":
                        temp_num.insert(opIndex, left - right)
                    else:
                        temp_num.insert(opIndex, left * right)
                except:
                    break

        # 최종 계산 결과가 최대값을 갖는지 확인
        result = abs(temp_num[0])
        if result > answer:
            answer = result
    return answer