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

programmers.co.kr/learn/courses/30/lessons/67257?language=swift

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

 

연산자 우선순위를 조정하여 주어진 수식을 최대화하는 문제이다. 

 

일반적인 연산의 경우 곱셉,나눗셈을 먼저 하나 여기서는 지정해주는 순서대로 무조건 연산해야한다.  

즉 - > * > + 의 순서일 수도 있고, * > + > -의 순서일 수 있다. 

그저 연산 결과가 최대의 값이면 되는 것이다. 

 

우선 가능한 연산자의 순서를 모두 구해야한다. 

재귀나 다른 방식으로 짜기도 하던데, 우선 일반 for문으로 구성하였다. 

func comb(_ a: [String]) -> [[String]] {
    var result = [[String]]()
    
    for s1 in a {
        var temp = [String]()
        temp.append(s1)
        for s2 in a {
            if !temp.contains(s2) {
                temp.append(s2)
            }            
        }
        if !result.contains(temp){
            result.append(temp)    
        }        
    }
    for s1 in a.reversed() {
        var temp = [String]()
        temp.append(s1)
        for s2 in a.reversed() {
            if !temp.contains(s2) {
                temp.append(s2)
            }            
        }
        if !result.contains(temp){
            result.append(temp)    
        } 
    }
    
    return result
}

연산자가 총 3개이기 때문에 3!로 6가지 경우의 수가 나오게 된다. 

 

이제 해야하는 것은 주어진 문자에서 숫자와 연산자를 걸러내는 것이다. 

그 이후, 순서에 맞게 연산한 결과를 최댓값과 비교하여 저장할지 버릴지 결정해주면 된다!

 

import Foundation

func solution(_ expression:String) -> Int64 {
    var numbers = expression.components(separatedBy: ["-","+","*"]).map {Int64($0)!}    
    let symbols = expression.map {Character(String($0))}.filter {!$0.isNumber}
    var orders = comb(Array(Set(symbols).map { String($0) }))
    var result: Int64 = 0
    
    for order in orders {
        var nums = numbers, opers = symbols
        for sym in order {
            let sym = Character(sym)
            while opers.contains(sym) {
                if let idx = opers.firstIndex(of: sym)  {
                    switch sym {
                    case "*":
                        nums[idx] *= nums[idx+1]
                    case "+":
                        nums[idx] += nums[idx+1]
                    case "-":
                        nums[idx] -= nums[idx+1]
                    default:
                        break
                    }
                    nums.remove(at: idx+1)
                    opers.remove(at:idx)                           
                }                                         
            }
        }
        let res = abs(nums[0])
        if res > result {
            result = res
        }
    }
    return result
}

유의해야 할 부분은 idx를 매번 새로 찾아서 범위에 맞도록 해줘야 한다. 

즉 idx를 미리 구하고 원소들을 제거해버리면 값이 안맞기에 주의해야하는 것이다. 

또한 연산자도 연산이 끝나고 나면 삭제해준다. 

 

[프로세스]

1. 연산자들의 나열 가능한 경우의 수를 구한다. 

2. 연산자와 숫자를 분리한다. 

3. 경우의 수에 따라 계산할 경우 값을 계산한다. 

    3-1. 최대값일 경우 저장 

4. 결과 리턴!

 

---

조금만 생각하면 쉽게 풀 수 있는 문제! 

다만 마지막 연산하는데 있어 조금 헤맨 것 같다. index를 매번 새로 구해줬어야 했는데, 그러지 않고 +,- 해주려다보니 엇갈렸던 것 같다. 

조금 더 넓은 시야를 가질 필요가 있는 것 같다! 

 

조금 막힌다면 더 넓은 범위에서 해결방안 찾아보기.

 

 

import Foundation

func solution(_ expression:String) -> Int64 {
    var numbers = expression.components(separatedBy: ["-","+","*"]).map {Int64($0)!}    
    let symbols = expression.map {Character(String($0))}.filter {!$0.isNumber}
    var orders = comb(Array(Set(symbols).map { String($0) }))
    var result: Int64 = 0
    
    for order in orders {
        var nums = numbers, opers = symbols
        for sym in order {
            let sym = Character(sym)
            while opers.contains(sym) {
                if let idx = opers.firstIndex(of: sym)  {
                    switch sym {
                    case "*":
                        nums[idx] *= nums[idx+1]
                    case "+":
                        nums[idx] += nums[idx+1]
                    case "-":
                        nums[idx] -= nums[idx+1]
                    default:
                        break
                    }
                    nums.remove(at: idx+1)
                    opers.remove(at:idx)                           
                }                                         
            }
        }
        let res = abs(nums[0])
        if res > result {
            result = res
        }
    }
    return result
}

func comb(_ a: [String]) -> [[String]] {
    var result = [[String]]()
    
    for s1 in a {
        var temp = [String]()
        temp.append(s1)
        for s2 in a {
            if !temp.contains(s2) {
                temp.append(s2)
            }            
        }
        if !result.contains(temp){
            result.append(temp)    
        }        
    }
    for s1 in a.reversed() {
        var temp = [String]()
        temp.append(s1)
        for s2 in a.reversed() {
            if !temp.contains(s2) {
                temp.append(s2)
            }            
        }
        if !result.contains(temp){
            result.append(temp)    
        } 
    }
    
    return result
}