[Programmers] 수식 최대화 (Level 2)

문제

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

프로그래머스

문제 요약

연산자가 "+", "-", "*(곱셈)" 3가지가 있는 수식이 있습니다.

연산자들의 우선순위는 같은 게 없고, 항상 우위에 있는 게 있습니다. 

연산자의 우선순위를 예를 들면,

*(곱셈), + > - (❎)

*(곱셈) > + > - (✅)

*(곱셈) > - > + (✅)

와 같이 동일한 우선순위를 정의할 수 없습니다. 

이런 상황에서 연산 수식을 최대화할 때의 상금 금액을 구하는 문제입니다.

풀이

연산자는 (+,-,*곱셈) 3가지밖에 없습니다.

그러므로 연산자의 우선순위가 나올 수 있는 경우의 수는 총 6가지입니다.

 

"+", "-", "*",

"+", "*", "-"

"-", "+", "*"

"-", "*", "+"

"*", "+", "-"

"*", "-", "+"

 

이 6가지 경우는 dfs로 구할 수도 있지만,

얼마 되지 않기 때문에 다 적어놓아도 됩니다. 

 

var numbersFiltered: [[String]] = []
var visited: [Bool] = Array.init(repeating: false, count: numbers.count)

func dfs(now: [String]) {
    if now.count == 3 {
        numbersFiltered.append(now)
        return
    }
    for i in 0..<operators.count {
        if visited[i] == false {
            visited[i] = true
            dfs(now: now + [operators[i]])
            visited[i] = false
        }
    }
}
dfs(now: [])

 

각 연산자 우선순위 경우마다 수식을 직접 계산해주었습니다. 

수식을 계산해줄 때, 연산자의 우선순위가 있기 때문에 일반적으로 계산해주면 안되고 연산자로 for문을 돌려주어야 합니다.

단순 브루트포스 문제네용

 

수식을 계산할 때 주의할 점은 연산자를 계산해준 후 다음

기존 계산한 숫자를 제거하고 다시 계산을 위해 배열에 넣어줄 때

out of index error가 나면 안됩니다. 

 

만일 2*3+2 의 수식에서 +를 계산한다고 가정해봅시다.

index = 3 일 때 +를 만납니다. 

그럼 index-1, index, index+1을 지우고 index-1 자리에 5를 삽입해야 합니다. (저는 이 곳에서 오류났어요.)

expressionArray.remove(at: index)
expressionArray.remove(at: index)
expressionArray.remove(at: index-1)
expressionArray.insert(String(result), at: index-1)

다른 사람 풀이를 보니 숫자와 operator를 따로 2개의 배열에 저장해놓았는데 이렇게 풀 경우 위와 같은 주의를 하지 않아도 되네용 

참고 하시면 좋을 듯 해요 ㅎㅎ 

 

전체 코드 

import Foundation

func calculate(num1: Int, num2: Int, operatorString: String) -> Int {
    if operatorString == "+" {
        return num1 + num2
    } else if operatorString == "-" {
        return num1 - num2
    } else {
        return num1 * num2
    }
    return 0
}

func solution(_ expression:String) -> Int64 {

    // MARK: +, -, * 경우의 수 모두 구하기 -> 6가지
    let operators: [String] = ["+","-","*"]
    var numbersFiltered: [[String]] = []
    var visited: [Bool] = Array.init(repeating: false, count: operators.count)
    func dfs(now: [String]) {
        if now.count == 3 {
            numbersFiltered.append(now)
            return
        }

        for i in 0..<operators.count {
            if visited[i] == false {
                visited[i] = true
                dfs(now: now + [operators[i]])
                visited[i] = false
            }
        }
    }
    dfs(now: [])

    var maxAnswer: Int64 = 0 // 답
    for numbersFilter in numbersFiltered {

        // MARK: expression을 배열로 만들기
        var expressionArray: [String] = []
        var temp: String = ""
        for i in 0..<expression.count {
            let chr = String(Array(expression)[i])
            if chr == "+" || chr == "-" || chr == "*" {
                expressionArray.append(temp)
                if chr == "+" { expressionArray.append("+") }
                else if chr == "-" { expressionArray.append("-") }
                else { expressionArray.append("*") }
                temp = ""
            } else {
                temp.append(chr)
            }
        }
        expressionArray.append(temp)

        // MARK: 수식 계산하기 
        var answer: Int64 = 0
        for number in numbersFilter {
            var index: Int = 0
            while expressionArray.count > 1, index < expressionArray.count {
                if expressionArray[index] == number {
                    let result = Int64(calculate(
                        num1: Int(expressionArray[index-1])!,
                        num2: Int(expressionArray[index+1])!,
                        operatorString: number
                    ))
                    expressionArray.remove(at: index)
                    expressionArray.remove(at: index)
                    expressionArray.remove(at: index-1)
                    expressionArray.insert(String(result), at: index-1)
                    answer = result
                    index = 0
                } else {
                    index += 1
                }
            }
        }
        maxAnswer = max(abs(answer), maxAnswer)
    }
    return maxAnswer
}