[Algorithm] 수식 최대화

[hwangJi-dev]

💬 문제

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

💬 Idea

1. 숫자를 저장하는 numArr와, 연산 기호를 차례대로 저장하는 operArr 배열을 만든다.
2. 그리고 순열을 통해 연산 우선순위 조합들을 구해 formulaPermutation 배열에 저장해준다.
3. 이후 formulaPermutation을 돌며 calbyFomula 메서드를 호출하여 각 우선순위 수식별 절댓값을 구하고, 이를 maxValue와 비교하여 최댓값을 구해준다.

<calbyFomula 메서드 동작 방식>

1. 우선순위를 돌며 [”+”, “-”, “*”] 연산 기호가 차례대로 저장되어있는 operArr에 해당 우선순위가 들어있을 때까지 반복한다.
   1. operArr에서 해당 연산기호의 첫 인덱스를 찾는다.
   2. 숫자들이 저장되어있는 numArr의 index, index + 1 2개의 숫자가 해당 연산기호로 연산되어야 할 숫자이므로 해당 두 인덱스에 해당하는 숫자를 연산기호에 맞게 연산해준다.
   3. 연산 결과를 index번째에 저장하고, 뒤에 있던 index + 1번은 배열에서 삭제해준다.
   4. 연산 기호도 연산이 끝났으므로 삭제해준다.
2. 이를 연산 우선순위가 끝날때까지 반복해준다.

💬 풀이

import Foundation

func solution(_ expression:String) -> Int64 {
    let numArr = expression.split(whereSeparator: { $0 == "+" || $0 == "*" || $0 == "-" }).map({ Int($0)! })
    let operArr = expression.split(whereSeparator: { $0.isNumber }).map({ String($0) })
    let formulaPermutation = permutation(Array(Set(operArr)), Set(operArr).count)
    var maxValue = 0
    
    for i in formulaPermutation {
        maxValue = max(maxValue, calbyFormula(i, operArr, numArr))
    }
    
    return Int64(maxValue)
}

// 우선순위 수식 기반으로 값을 계산하는 메서드
func calbyFormula(_ priority: [String], _ operArr: [String], _ numArr: [Int]) -> Int {
    var numArr = numArr
    var operArr = operArr
    
    for i in priority {
        while operArr.contains(String(i)) {
            let idx = operArr.firstIndex(of: String(i)) ?? -1
            
            if i == "*" {
                numArr[idx] = numArr[idx] * numArr[idx + 1]
            } else if i == "+" {
                numArr[idx] = numArr[idx] + numArr[idx + 1]
            } else {
                numArr[idx] = numArr[idx] - numArr[idx + 1]
            }
            
            numArr.remove(at: idx + 1)
            operArr.remove(at: idx)
        }
    }
    
    return abs(numArr[0])
}

// 순열 생성 메서드
func permutation(_ array: [String], _ n: Int) -> Set<[String]> {
    var result = Set<[String]>()
    if array.count < n { return result }

    var visited = Array(repeating: false, count: array.count)

    func cycle(_ now: [String]) {
        if now.count == n {
            result.insert(now)
            return
        }

        for i in 0..<array.count {
            if visited[i] {
                continue
            } else {
                visited[i] = true
                cycle(now + [array[i]])
                visited[i] = false
            }
        }
    }

    cycle([])

    return result
}