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

내가 했던 삽질

이 문제는 정말 삽질을 많이 했던.. 그리고... 정말 오래걸렸던 문제이다.
일단 처음에 BFS를 사용하려고 했고, 정규표현식을 사용하려고 했었다. .. 그러다가 점점 산으로 갔다. 아무튼 !!!
문제 해석 + 요구사항을 확인해보자.

1. 문제 해석

주어진 사칙연산의 개수는 *,-,+ 3가지 이다.
3가지를 활용해서 만들 수 있는 모든 연산순위를
주어진 문자열에 이용하여 연산했을 때 나올 수 있는 최대값을 구하기

2. 요구사항

1) *,-,+ 3가지 연산자를 활용하자 -> 여기서 3!임으로 6가지 밖에 없어 특별히 combination을 사용할 필요가 없다.
2) 주어진 문자열 패턴에서 연산자 순위를 적용해 우선풀이

3. 내가 실수한 것

1) 내가 만들려고 했던 함수는 다음과 같다.

• 3가지 연산자를 이용해 연산순서의 경우를 모두 추출해주는 함수
  -> 만들 필요가 없었다.
• 정규표현식을 이용해 숫자 연산자 숫자 패턴을 추출하여 계산 하는 것!
  -> 예외 케이스를 생각하지 못했다. 왜냐면 연산하고 나서
  1-2-3 와 같은 경우가 생기는데, 이렇게 하면 -1-3이 남고, 이것을 처리하지 못하게 된다.
  -> 패턴 자체가 없을때까지 계산해야 하는데 그럴수록 코드가 길어졌고, 다른 답안을 봐도 너무 이해하기 어려웠다.
• 아래는 내가 풀었던 풀이이다.

def extract_order(order=""):
    if len(order) == 3:
        result.append(order)
        return

    if "+" not in order:
        extract_order(order + "+")
    if "-" not in order:
        extract_order(order + "-")
    if "*" not in order:
        extract_order(order + "*")

def solution(expression):
    extract_order()
    max = -1111
    for i in result:
        temp = expression
        for j in i:
            if j == "-":
                cal_pattern = re.compile("[0-9]+-[0-9]+")
            else:
                cal_pattern = re.compile(f"[0-9]+[{j}][0-9]+")
            target_exe = cal_pattern.findall(temp)
            for k in target_exe:
                temp = temp.replace(k, str(eval(k)))

        if not temp.isdigit():
            temp = str(eval(temp))

        if int(abs(int(temp)))>max:
            max = abs(int(temp))

    return max

실제 모범답안

카카오 기술블로그를 참조하고, 생각보다 해설이 간단했다. 그만큼 간결한 코드일 것이라고 생각했다. 블로그를 뒤져보면서 가장 모범답안에 가까운 풀이를 찾아냈다.

import re

def solution(expression):
    answer = 0
    oper = ["+-*", "+*-", "-*+", "-+*", "*+-", "*-+"] # 어차피 6가지 밖에 없기 때문에 미리 배열에 담아둔다.
    for i in range(6):
        check = re.findall("[+*-]+", expression)
        numbers = re.findall("[0-9]+", expression)
        # 정규표현식을 사용해 숫자와 연산자를 모두 분리한다.
        for j in range(3): # 연산자를 하나씩 꺼내어 비교한다.
            k = 0
            while k < len(check): # 문자열에서 추출된 연산자의 개수 만큼 비교한다.
                if check[k] == oper[i][j]: # 여기서 oper[i][j]가 위의 oper배열에서 순서대로 하나씩 비교하는 것을 알 수 있음(연산자 순서가 보장됨)
                    numbers[k] = str(eval(numbers[k] + check[k] + numbers[k + 1])) # 여기서,, 1+2 라고 하면 연산자와 피연산자의 인덱스 는 같거나 1차이라는 특징을 이용했다. 정말 완벽한 풀이!
                    del check[k] #이후, 연산된 결과를 제외시켜준다.
                    del numbers[k + 1] # 피연산자는 numbers[k]로만들어준다. 나머지는 삭제
                else:
                    k += 1 # 순서와 맞지않으면 다음 연산자를 확인하는 방식이다.
        answer = max(answer, abs(int(numbers[0])))
    return answer

너무 완벽한 풀이이다. 해당 풀이를 주석으로 설명했다.

 

안보고 풀어보기

안보고 풀어봤더니 2가지 실수를 했다.

import re

result = []
def extract_order(order=""): # 이거는 bfs연습겸 그냥 했다.
    if len(order) == 3:
        result.append(order)
        return

    if "+" not in order:
        extract_order(order + "+")
    if "-" not in order:
        extract_order(order + "-")
    if "*" not in order:
        extract_order(order + "*")

def solution(expression):
    extract_order()
    oper = result
    answer = -111
    for i in range(6):
        check = re.findall("[*+-]+",expression)
        numbers = re.findall("[0-9]+",expression)
        k = 0
        temp = 0
        for j in range(3):
            while k <len(check):
                if check[k] == oper[i][j]:
                    numbers[k]=str(eval(numbers[k]+check[k]+numbers[k+1]))
                    del numbers[k+1]
                    del check[k]
                else:
                    k+=1
        temp = abs(int(numbers[0]))
        
        if answer< temp:
            answer = temp
            
    return answer

k를 while문 위에서 초기화 해야 하는데, 왜 아래서 한겨... 그리고 numbers는 마지막에 [원소] 이런 형태라는걸 생각했어야 한다. 아무튼 오늘 포스팅을 끝낸다.