[Problem Solving] 프로그래머스 67257 수식 최대화

문제 설명은 다음 링크를 참고해주시기 바랍니다. 문제 설명

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

해당 문제는 ("*", "+", "-") 이하 operation과 정수로 이루어진 식을 문자열로 제시하면 operation의 우선순위들을 바꿔가면서 크기가 가장 큰 결과를 반환하는 문제입니다. 

 

문제 해결을 위해서는 어떤 우선순위가 가장 크기가 큰 결과를 반환하는지 모르기 때문에 모든 우선순위에 대해서 조사를 진행합니다. 또한 operation과 정수로 이뤄진 식에서 정수와 operation을 다르게 처리를 해야 하기 때문에 이 둘을 분리하여 계산해야 합니다.

 

수식 최대화는 stack과 permutation을 사용하는 문제로 해결 순서는 다음과 같습니다.

1. 순열을 사용하여 ("*", "+", "-")의 모든 경우의 수를 만들어준다.
2. 임의의 경우의 수를 선택한다.
3. 주어진 식을 정수와 기호로 나눠 data에 저장한다.
4. 높은 우선순위의 기호를 선택한다.
5. data에서 값을 하나씩 가져와 current에 저장하고, 4의 결과와 비교한다.
6. 5의 결과가 참이라면 current는 기호이므로 stack의 마지막 값과 data의 첫 번째 값을 가져와 계산하여 stack에 저장한다.
7. 5의 결과가 거짓이라면 current는 정수이므로 stack에 저장한다.
8. 5를 반복한다.
9. data가 빈 값이므로 stack의 값을 data에 초기화해준다.
10. 4를 반복한다.
11. 10이 끝난 결과의 최댓값을 answer에 저장한다.
12. 2를 반복한다.

문제에서 제공한 예시를 통해서 4~9번의 순서를 자세하게 알아보겠습니다.

ex) expression="100-200*300-500+20", priorities=("*", "+", "-"), answer = 60420

 

step.0

 

data = ["100", "-", "200", "*", "300", "-", "500", "+", "20"]

100

-

200

*

300

-

500

+

20

stack = []

---

step.1

data = ["100", "-", "200", "*", "300", "-", "500", "+", "20"], priority = "*"

100

-

200

*

300

-

500

+

20

stack = ["100", "-", 60000, "-", "500", "+", "20"]

100

-

60000

-

500

+

20

---

step.2

data = ["100", "-", 60000, "-", "500", "+", "20"], priority = "+"

100

-

60000

-

500

+

20

stack  = ["100", "-", 60000, "-", 520]

100

-

60000

-

520

---

step.3

data  = ["100", "-", 60000, "-", 520], , priority = "-"

100

-

60000

-

520

stack = [-60420]

-60420

---

stack에는 현재 선택된 우선순위 기호 전까지의 식이 저장되고, data에는 우선순위 기호 후의 식이 저장되어 있습니다. 다시 말해 이 순간의 current는 기호이고, stack의 마지막 값과 data의 첫번째 값이 계산되어야 할 정수입니다. 따라서 해당 값들을 이용하여 결괏값을 계산하고 stack에 저장해줍니다.

 

다음은 해결 순서를 코드로 구현한 것입니다.

 

# 프로그래머스 No.67257 수식 최대화
from itertools import permutations

def get_data_by(expression):
  data = []
  temp = ""
  for s in expression:
    if s.isdigit():
      temp += s
    else:
      data.append(temp)
      data.append(s)
      temp = ""
  data.append(temp)
  return data

def calculate_by_priorities(data, priorities):
  for priority in priorities:
    stack = []
    while data:
      current = data.pop(0)
      if current == priority: # current is operation and same as priority
        stack.append(calculate_by(current, stack.pop(), data.pop(0)))
      else:
        stack.append(current)
    data = stack # data is empty. initialize data by stack
  return abs(data[0])

def calculate_by(operation, num1, num2):
  num1, num2 = int(num1), int(num2)
  if operation == '-':
    return num1 - num2
  elif operation == '+':
    return num1 + num2
  else:
    return num1 * num2

def solution(expression):
  answer = 0
  priorities = list(permutations(("*", "+", "-"), 3))

  for priority in priorities:
    data = get_data_by(expression)
    answer = max(answer, calculate_by_priorities(data ,priority))
  return answer

 

구현된 함수에 대한 설명입니다.

• get_data_by(expression): 주어진 식을 정수와 operation으로 분리하는 결과를 함수입니다.
• calculate_by_priorities(data, priorities): priorities에 의해 계산된 결과를 반환하는 함수입니다.
• calculate_by(operation, num1, num2): 정수 2개를 operation으로 계산한 결과를 반환하는 함수입니다.
• solution(expression): 모든 우선순위에 대해서 calculate_by_priorities를 계산하고, 가장 크기가 큰 결과를 반환하는 함수입니다.

처음 문제를 접근할 때 정수와 기호를 분리하여 각각의 배열에 저장하여 우선순위에 맞는 기호의 index를 기준으로 결과를 저장하는 방식을 택하였습니다. 이 방식은 자료구조를 제대로 활용하지 못한 방법으로 각 계산마다 정수와 기호에서 값을 하나씩 제거하여 index의 값이 배열의 길이를 넘는 오류를 발생하게 됩니다.

 

이 문제를 계기로 코딩 테스트 문제를 해결할 때에는 어떤 알고리즘을 사용할 것인지 어떤 자료구조를 선택할 것인지에 대해서 확실하게 결정하고 문제 해결에 들어가야 한다는 깨달음을 얻었습니다.