[프로그래머스 lv2] 수식 최대화 (파이썬)

2020 카카오 인턴십 문제입니다.

 

문제 설명

IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다.

이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 같은 방식으로 결정하려고 합니다.

해커톤 대회에 참가하는 모든 참가자들에게는 숫자들과 3가지의 연산문자(+, -, *) 만으로 이루어진 연산 수식이 전달되며, 참가자의 미션은 전달받은 수식에 포함된 연산자의 우선순위를 자유롭게 재정의하여 만들 수 있는 가장 큰 숫자를 제출하는 것입니다.

단, 연산자의 우선순위를 새로 정의할 때, 같은 순위의 연산자는 없어야 합니다. 즉, + > - > * 또는 - > * > + 등과 같이 연산자 우선순위를 정의할 수 있으나 +,* > - 또는 * > +,-처럼 2개 이상의 연산자가 동일한 순위를 가지도록 연산자 우선순위를 정의할 수는 없습니다. 수식에 포함된 연산자가 2개라면 정의할 수 있는 연산자 우선순위 조합은 2! = 2가지이며, 연산자가 3개라면 3! = 6가지 조합이 가능합니다.

만약 계산된 결과가 음수라면 해당 숫자의 절댓값으로 변환하여 제출하며 제출한 숫자가 가장 큰 참가자를 우승자로 선정하며, 우승자가 제출한 숫자를 우승상금으로 지급하게 됩니다.

 

예를 들어, 참가자 중 네오가 아래와 같은 수식을 전달받았다고 가정합니다.

 

"100-200*300-500+20"

 

일반적으로 수학 및 전산학에서 약속된 연산자 우선순위에 따르면 더하기와 빼기는 서로 동등하며 곱하기는 더하기, 빼기에 비해 우선순위가 높아 * > +,- 로 우선순위가 정의되어 있습니다.대회 규칙에 따라 + > - > * 또는 - > * > + 등과 같이 연산자 우선순위를 정의할 수 있으나 +,* > - 또는 * > +,- 처럼 2개 이상의 연산자가 동일한 순위를 가지도록 연산자 우선순위를 정의할 수는 없습니다.

수식에 연산자가 3개 주어졌으므로 가능한 연산자 우선순위 조합은 3! = 6가지이며, 그 중 + > - > * 로 연산자 우선순위를 정한다면 결괏값은 22,000원이 됩니다.

반면에 * > + > - 로 연산자 우선순위를 정한다면 수식의 결괏값은 -60,420 이지만, 규칙에 따라 우승 시 상금은 절댓값인 60,420원이 됩니다.

 

참가자에게 주어진 연산 수식이 담긴 문자열 expression이 매개변수로 주어질 때, 우승 시 받을 수 있는 가장 큰 상금 금액을 return 하도록 solution 함수를 완성해주세요.

 

[제한사항]

• expression은 길이가 3 이상 100 이하인 문자열입니다.
• expression은 공백문자, 괄호문자 없이 오로지 숫자와 3가지의 연산자(+, -, *) 만으로 이루어진 올바른 중위표기법(연산의 두 대상 사이에 연산기호를 사용하는 방식)으로 표현된 연산식입니다. 잘못된 연산식은 입력으로 주어지지 않습니다.
  • 즉, "402+-561*"처럼 잘못된 수식은 올바른 중위표기법이 아니므로 주어지지 않습니다.
• expression의 피연산자(operand)는 0 이상 999 이하의 숫자입니다.
  • 즉, "100-2145*458+12"처럼 999를 초과하는 피연산자가 포함된 수식은 입력으로 주어지지 않습니다.
  • "-56+100"처럼 피연산자가 음수인 수식도 입력으로 주어지지 않습니다.
• expression은 적어도 1개 이상의 연산자를 포함하고 있습니다.
• 연산자 우선순위를 어떻게 적용하더라도, expression의 중간 계산값과 최종 결괏값은 절댓값이 263 - 1 이하가 되도록 입력이 주어집니다.
• 같은 연산자끼리는 앞에 있는 것의 우선순위가 더 높습니다.

입출력 예

입출력 예

 

입출력 예 설명

입출력 예 #1
* > + > - 로 연산자 우선순위를 정했을 때, 가장 큰 절댓값을 얻을 수 있습니다.
연산 순서는 아래와 같습니다.

100-200*300-500+20
= 100-(200*300)-500+20
= 100-60000-(500+20)
= (100-60000)-520
= (-59900-520)
= -60420

따라서, 우승 시 받을 수 있는 상금은 |-60420| = 60420 입니다.

 

입출력 예 #2
- > * 로 연산자 우선순위를 정했을 때, 가장 큰 절댓값을 얻을 수 있습니다.
연산 순서는 아래와 같습니다.(expression에서 + 연산자는 나타나지 않았으므로, 고려할 필요가 없습니다.)

50*6-3*2
= 50*(6-3)*2
= (50*3)*2
= 150*2
= 300

따라서, 우승 시 받을 수 있는 상금은 300 입니다.

 

 

 

 

---

나의 풀이

문제가 길어서 꽤 어려워 보이지만 설명이 자세해서 그런 것이지 문제를 이해하기에 생각보다 어렵지 않았다.

핵심은 연산자들을 조합해 모든 상황에서 값을 구해 비교하는 완전탐색 문제이다.

이 문제의 관건은 '연산자를 어떻게 조합할 것인가'와 '각 우선순위의 경우에 대해 어떻게 연산을 처리 할 것인가' 이다.

 

우선 연산자를 어떻게 조합할 지에 대한 문제는 itertools 라이브러리의 permutations를 사용해 쉽게 구현할 수 있었다.

permutations는 n개를 뽑아내 순서대로 조합하는 것이다. (순열)

여기서는 ops에 "*", "+", "-" 를 저장하고 permutations(ops)로 연산자를 뽑아 나열했다.

 

그리고 연산 처리 부분에서는 2개의 큐를 사용했다. 이 부분은 소스코드를 보며 설명하도록 한다.

 

 

우선 매개 변수로 받은 expression을 연산자를 기준으로 쪼갤 것이다.

정규표현식 라이브러리인 re의 split을 사용하면 간단하게 쪼갤 수 있지만 re를 사용하지 않고 무식하게 쪼개봤다.

# 스택 생성
    li = []
    s = 0
    for i, v in enumerate(expression):
        if v in ["*", "+", "-"]:
            li.append(expression[s:i])
            li.append(v)
            s = i + 1
    else:
        li.append(expression[s:])
        
    stacks = [deque(li), deque()]

우선 enumerate()로 expression을 순회하며 연산자가 등장하면 연산자 앞까지 등장한 숫자들을 리스트에 넣고, 연산자도 리스트에 넣는다.

인덱스는 i와 s로 관리한다.

이렇게 마지막 연산자까지 입력하면 마지막 연산자 뒤에 있는 숫자가 남는다.

이 숫자를 해결하기 위해서 for ~ else 문을 사용했다.

for ~ else문이란, 반복문 뒤에 else를 붙이면 반복이 완료된 후 무조건 한번 실행하는 코드를 else에 작성할 수 있다.

 

소스코드에서 expression을 쪼갠 리스트는 li이고, 이 li를 deque()를 사용해 큐로 만들어준다.

그리고 비어있는 다른 큐를 만들어 이 두개의 큐를 하나의 리스트로 관리한다.

 

# expression에 없는 연산자는 ops에서 제거
    for op in ops:
        if op not in expression:
            ops.remove(op)
            
    # ops에 있는 연산자로 구성할 수 있는 모든 우선순위 생성
    primarity = permutations(ops)

expression에 없는 연산자는 ops 리스트에서 제거해주고, 소스코드 위에서 말한 permutations로 연산자 순열을 생성한다. 이 값은 순회 가능한 iterable 객체가 된다. (primarity에 저장)

 

 

 

 

이 primarity에는 최대 6가지의 우선순위 조합이 있다. 문제를 잘 읽어보면 언급되어 있듯이 3개의 연산자로 만들 수 있는 조합은 3! = 6가지 이다.

연산자가 2개로 이루어졌다면 조합은 2! = 2가지 이다.

최대 6가지 조합이기 때문에 연산에 큰 부담이 될 것 같지는 않다.

 

만약 3개의 연산자(+, -, *)가 조합된 경우 (+, -, *), (+, *, -), (-, +, *) ... 이 되고, 각각의 경우에서 연산을 처리할 것이다.

for case in primarity: # 최대 6가지의 연산자 우선순위 조합
	stacks 초기화
	for c in case: # 각 경우에서 연산자 처리
		while 스택1에 데이터가 있으면 반복:
        	스택1에서 데이터 하나를 빼서
            만약 스택2의 마지막 데이터가 계산 중인 연산자라면
            	연산자와 그 이전에 입력된 데이터를 꺼내 계산을 하고
            스택2에 저장한다.
    # 반복문을 한번 돌면 연산자가 하나씩 처리된다.
    # 그리고 스택1 -> 스택2가 된다.
    
    result = 결과 의 절대값
	answer = max(answer, result)

처리 과정은 위 설명과 같다.

 

전체 소스코드

from itertools import permutations
from collections import deque

def solution(expression):
    answer = 0
    ops = ["*", "+", "-"]
    
    # 스택 생성
    li = []
    s = 0
    for i, v in enumerate(expression):
        if v in ["*", "+", "-"]:
            li.append(expression[s:i])
            li.append(v)
            s = i + 1
    else:
        li.append(expression[s:])
    
    # expression에 없는 연산자는 ops에서 제거
    for op in ops:
        if op not in expression:
            ops.remove(op)
            
    # ops에 있는 연산자로 구성할 수 있는 모든 우선순위 생성
    primarity = permutations(ops)
    
    for case in primarity: # 최대 6가지의 연산자 우선순위 조합
        stacks = [deque(li), deque()]
        t1 = 1
        for c in case: # 각 경우에서 연산자 처리
            t1 = (t1+1) % 2 # 스택 토글 변수
            t2 = (t1+1) % 2
            while len(stacks[t1]):
                item = stacks[t1].popleft()
                if len(stacks[t2]) and stacks[t2][-1] == c:
                    c = stacks[t2].pop()
                    n = stacks[t2].pop()
                    item = str(eval(str(n)+c+str(item)))
                stacks[t2].append(item)
            
        result = stacks[len(ops)%2].pop()
        result = abs(int(result))
        answer = max(answer, result)
            
    return answer

 

테스트 결과