Swift ) 프로그래머스(Lv2) - 수식 최적화 (Permutation)

programmers.co.kr/learn/courses/30/lessons/67257

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

안녕하세요 후르륵짭짭 입니다.

이번 문제는 카카오 답게 문자열을 나누고 짜르고 다루는 문제였습니다.

실제로 테스트로 만났을 때는,,, 못 풀었던 문제였는데,,,,

이제는 풀 수 있게 되었습니다.

 

** 나의 풀이 **

var list : [[String]] = []

func solution(_ expression:String) -> Int64 {
    
    var answer : Int64 = 0
    
    let getFunction = expression.filter { (char) -> Bool in
        return !char.isNumber
    }.map { (char) -> String in
        return String(char)
    }
    
    let getNumber = expression.components(separatedBy: ["-","*","+"])
    
    let makeSetArray = Array(Set(getFunction))
    
    
    
    var funcAndNum : [String] = [getNumber[0]]
    
    for (index , element ) in getFunction.enumerated() {
        
        funcAndNum.append(element)
        funcAndNum.append(getNumber[index + 1])
        
    }
    
    permutaion(makeSetArray, 0, [] , makeSetArray.count)
    
    for element in list {
        var calculate = false
        var tempStack : [String] = []
        var tempFuncAndNum = funcAndNum
        
        for item in element {
            
            
            for single in tempFuncAndNum {
                
                
                if single != "+" && single != "-" && single != "*"{
                
                    if calculate {
                        //작업해줘야한다.
                        
                        var newNumber : Int64 = 0
                        let popLastNum  = tempStack.removeLast()
                        
                        switch item {
                        case "+":
                            newNumber = Int64(popLastNum)! + Int64(single)!
                        case "-":
                            newNumber = Int64(popLastNum)! - Int64(single)!
                        default:
                            newNumber = Int64(popLastNum)! * Int64(single)!
                        }
                        
                        tempStack.append(String(newNumber))
                        
                        calculate = false
                    }
                    else{
                        tempStack.append(single)
                    }
                    
                }
                else{
         
                    
                    if single == item {
                       
                        calculate = true
                    }
                    else{
                        tempStack.append(single)
                    }
                    
                    
                }
            
                
            }
            
              tempFuncAndNum = tempStack
            tempStack = []
            
        }
        
        //숫자 계산
        answer = max(answer , abs(Int64(tempFuncAndNum.first!)!) )
        
    }
    
    
    return answer
}

func permutaion(_ array : [String],_ current : Int, _ sum : [String] , _ total : Int){
    
    var temp = array
    var tempSum = sum
    
    if current  == total {
        
        list.append(tempSum)
    }
    else{
        
        for index in 0..<array.count {
            
            let item = array[index]
            temp.remove(at: index)
            tempSum.append(item)
            permutaion(temp, current + 1 ,tempSum ,total)
            temp.insert(item, at: index)
            tempSum = sum
            
        }
        
    }
    
}

let expression = "50*6-3*2"

print(solution(expression))

코드가 쫌 많이 길지만,,,,

    let getFunction = expression.filter { (char) -> Bool in
        return !char.isNumber
    }.map { (char) -> String in
        return String(char)
    }
    
    let getNumber = expression.components(separatedBy: ["-","*","+"])
    

일단 이렇게 filter를 사용해서 + , - , * 를 뽑아주고 String으로 변형 시켜 줍니다. 그러면 공식만 가져오게 되고

그리고 separatedBy를 통해서 - , * + 가 있는 곳을 기준으로 나눠주도록 했습니다. 그러면 숫자만 가져오게 됩니다.

이제, - * + + + 이렇게 되어 있을 수도 있으니, 아래처럼 Set을 통해 중복된 것들을 제거 해줍니다.

    let makeSetArray = Array(Set(getFunction))

 이제, 스택으로 담아 줄 것 입니다. 

현재 getFunc 에는 + + -  가 있다고 가정하고 getNumber에는 100 200 300 400 있다고 가정하면

getNumber가 getFunc 보다 하나 더 많은 것을 확인 할 수 있습니다.

 var funcAndNum : [String] = [getNumber[0]]
    
    for (index , element ) in getFunction.enumerated() {
        
        funcAndNum.append(element)
        funcAndNum.append(getNumber[index + 1])
        
    }

그래서 위의 코드 처럼 String 배열로 두가지를 다 담아 뒀습니다. (100 + 200 + 300 - 400 이런 형태가 될 겁니다.)

이제 순열을 해줍니다.

func permutaion(_ array : [String],_ current : Int, _ sum : [String] , _ total : Int){
    
    var temp = array
    var tempSum = sum
    
    if current  == total {
        
        list.append(tempSum)
    }
    else{
        
        for index in 0..<array.count {
            
            let item = array[index]
            temp.remove(at: index)
            tempSum.append(item)
            permutaion(temp, current + 1 ,tempSum ,total)
            temp.insert(item, at: index)
            tempSum = sum
            
        }
        
    }
    
}

이렇게 씨언어랑 다르게 check를 사용하지 않고 순열을 만들어 줬습니다.

그리고 마지막으로 3중 포문을 통해 탐색을 해줬습니다.

   for element in list {
        var calculate = false
        var tempStack : [String] = []
        var tempFuncAndNum = funcAndNum
        
        for item in element {
            
            
            for single in tempFuncAndNum {
                
                
                if single != "+" && single != "-" && single != "*"{
                
                    if calculate {
                        //작업해줘야한다.
                        
                        var newNumber : Int64 = 0
                        let popLastNum  = tempStack.removeLast()
                        
                        switch item {
                        case "+":
                            newNumber = Int64(popLastNum)! + Int64(single)!
                        case "-":
                            newNumber = Int64(popLastNum)! - Int64(single)!
                        default:
                            newNumber = Int64(popLastNum)! * Int64(single)!
                        }
                        
                        tempStack.append(String(newNumber))
                        
                        calculate = false
                    }
                    else{
                        tempStack.append(single)
                    }
                    
                }
                else{
         
                    
                    if single == item {
                       
                        calculate = true
                    }
                    else{
                        tempStack.append(single)
                    }
                    
                    
                }
            
                
            }
            
              tempFuncAndNum = tempStack
            tempStack = []
            
        }
        
        //숫자 계산
        answer = max(answer , abs(Int64(tempFuncAndNum.first!)!) )
        
    }
    
    
    return answer
}