[프로그래머스] 카카오 2020 인턴십 - 수식 최대화 [Swift]

문제 링크

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

문제 풀이

이 문제는 +,-,* 연산자가 포함된 수식이 하나 주어지고 해당 수식에 존재할 수 있는 연산자 우선순위들의 모든 경우를 계산해서 절댓값의 최댓값이 나오도록 만드는 문제입니다.

 

하나의 예를 보면,

 

100-200*300-500+20

 

위와 같은 수식이 주어졌다고 가정했을 때 해당 수식이 갖는 연산자는 +,-,* 입니다. 

따라서 연산자 우선순위로는 (+,-,*), (-,+,*), (+,*,-), (-,*,+), (*,+,-), (*,-,+)로 총 6가지가 존재합니다.

이렇게 만들어진 우선순위로 모두 계산을 해보면 (*,+,-)로 연산자 우선순위를 정했을 때 가장 큰 절댓값인 60420을 얻을 수 있어요.

 

따라서 문제를 해결하기 위해선

1. 주어진 수식을 연산자와 숫자로 구분한다.
2. 주어진 수식에 포함된 연산자로 만들 수 있는 모든 우선순위 조합을 만든다.
3. 만들어진 우선순위 조합으로 모두 계산해서 절대값이 가장 큰 값을 찾는다

위와 같은 과정을 수행해주면 됩니다.

저는 모든 우선순위 조합을 DFS로 구해서 문제를 해결했습니다.

소스 코드

import Foundation

func solution(_ expression:String) -> Int64 {
    var num: [Int64] = []
    var operators: [String] = []
    var temp: String = ""
    // 주어진 식에서 연산자와 숫자를 나눈다.
    for i in expression {
        if i == "-" || i == "+" || i == "*" {
            num.append(Int64(temp)!)
            operators.append(String(i))
            temp = ""
        } else {
            temp += String(i)
        }
    }
    
    num.append(Int64(temp)!)
    
    // 연산자가 중복해서 들어있을 수 있기 때문에 중복제거
    let operatorList = Array(Set(operators))
    // 우선순위 조합들을 넣을 배열
    var prioritys: [[String]] = []
    var stack: [String] = []
    var visited: [Bool] = [Bool](repeating: false, count: operatorList.count)
    // 모든 연산자 우선순위를 만드는 dfs 함수
    func dfs() {
        if stack.count == operatorList.count {
            prioritys.append(stack)
            return
        }
        for i in 0..<operatorList.count {
            if !visited[i] {
                stack.append(operatorList[i])
                visited[i] = true
                dfs()
                stack.removeLast()
                visited[i] = false
            }
        }
    }
    
    dfs()
    
    // 결과를 저장할 값
    var nowResult: Int64 = Int64.min
    // 아까 만든 연산자 우선순위조합으로 모든 경우를 계산해본다
    for priority in prioritys {
        var nowNum = num
        // 식에 포함된 연산자를 가지고 옴
        var nowOperators = operators
        // 연산자 우선순위에 맞게 모두 처리
        for p in priority {
            var i = 0
            var tempNum = nowNum
            var tempOperators = nowOperators
            // 우선순위에 맞게 계산한다
            while i < tempOperators.count {
                if p == tempOperators[i] {
                    if p == "+" {
                        // 현재 i, i+1 위치의 값을 더한 값을 i에 저장
                        tempNum[i] = tempNum[i] + tempNum[i+1]
                        // i+1에 위치한 값은 제거
                        tempNum.remove(at: i+1)
                        // i위치의 연산자도 사용했기 때문에 제거
                        tempOperators.remove(at: i)
                        // i값 1 감소
                        i -= 1
                    } else if p == "-" {
                        tempNum[i] = tempNum[i] - tempNum[i+1]
                        tempNum.remove(at: i+1)
                        tempOperators.remove(at: i)
                        i -= 1
                    } else if p == "*" {
                        tempNum[i] = tempNum[i] * tempNum[i+1]
                        tempNum.remove(at: i+1)
                        tempOperators.remove(at: i)
                        i -= 1
                    }
                }
                // 현재 우선순위 연산자를 모두 계산한 뒤엔 i값 1 증가
                i += 1
            }
            nowNum = tempNum
            nowOperators = tempOperators
        }
        // 현재 계산된 값과 기존 값을 비교해서 최대값을 저장
        nowResult = max(nowResult, abs(nowNum[0]))
    }
    
    return nowResult
}