<프로그래머스> [카카오 인턴 2020] 수식 최대화

스위프트로 구현한 코드이다.

 

고민했던 점은 이걸 완전탐색으로 하는 수 밖에 없나 고민했었다. 근데 수식도 100자리 이하고, 연산 우선순위 바뀌는 경우도 12가지라 시간 복잡도를 계산하면 1초안에 들어와서 완탐을 목적으로 낸 문제가 맞다 생각했다. (다른 효율적인 방법이 있다면 댓글좀 ㅠㅠ)

 

또 고민의 과정은, 문자열을 어떻게 리스트로 파싱할지, parse는 안된다는 결론이 났다. +-*/ 네가지로 분할해야 되서, 그래서 리스트로 순회하면서 숫자랑 연산기호를 따로 읽고 저장하는 식으로 했다.

 

이제 연산을 해야되는데, 일반적으로 스택을 사용한 연산을 하는걸 알고 있다. 그런데 오래되서 스택으로 하는 방법을 아무리 생각해도 안나더라.,... 쉬운문제 부터 다시 해봐야 겠다.

 

그래서 스택을 사용하지 않고 리스트로 어떻게 연산을 할수 있을지 생각하다. 반복문 속에서 우선 순위가 높은 것을 순차적으로 연산하는 방식으로 했다.

 

완탐으로 연산자 우선순위를 구하기 위해 permutation도 배꼈는데, 이 또한 구현 법이 생각이 안났다... 

 

생각이 안난다고 그대로 쓰기도 좀 뭐하지만... 단순 암기로 하긴 싫어서, 과정을 최대한 이해해보려 하고있다.

import Foundation



func solution(_ expression:String) -> Int64 {
    var list: [String] = []
    var num: String = ""
    
    for (idx, val) in expression.enumerated() {
        let ch = val.description
        if ch == "+" || ch == "-" || ch == "*" || ch == "/" {
            if num != "" {
                list.append(num)
                num = ""
            }
            
            //print("1: \(ch)")
            list.append(ch)
            
        } else {
            //print("2: \(ch)")
            num += ch
        }
        
        if idx == expression.count - 1 {
            list.append(num)
        }
    }
    
    //print(list)
    var ops = ""
    for x in "+-*/" {
        if list.firstIndex(of: x.description) != nil {
            print("x: \(x)")
            ops += x.description
        }
    }

    
    return cal(operators: ops, list: list)
}

var perms: [Array<Character>] = []

func permutations(_ n:Int, _ a: inout Array<Character>) {
    if n == 1 { perms.append(a); return }
    for i in 0..<n-1 {
        permutations(n-1, &a)
        a.swapAt(n-1, (n%2 == 1) ? 0: i)
    }
    permutations(n-1, &a)
}

func cal(operators: String, list: [String]) -> Int64 {
    var max: Int64 = 0
    var ans: Int64 = 0
    
    var arr = Array(operators)
    permutations(arr.count, &arr)
    

    for z in perms {
        var through: [String] = list

        print("through: \(through)")
        var save: [String] = through
        let oper = String(z)
        for x in oper {
            let op = x.description
            
            save = []
            var skip: Bool = false
            for (idx, y) in through.enumerated() {
                let ch = y.description
                
                if ch == "+" || ch == "-" || ch == "*" || ch == "/" {
                    if ch == op {
                        let opr = String(cal2(op: ch, op1: save.last!, op2: through[idx + 1]))
                        print("opr: \(opr)")
                        save.popLast()
                        save.append(opr)
                        skip = true
                    } else {
                        save.append(ch)
                        skip = false
                    }
                } else {
                    if !skip {
                        save.append(ch)
                    }
                }
            }
            through = save
            print("through: \(through)")
            print("ans: \(ans)")
        }
        ans = Int64(through[0])!
        if ans < 0 {
            ans = -ans
        }
        if max < ans {
            max = ans
        }
    }

    
    return max
}

func cal2(op: String, op1: String, op2: String) -> Int64 {
    if op == "+" {
        return Int64(op1)! + Int64(op2)!
    } else if op == "-" {
        return Int64(op1)! - Int64(op2)!
    } else if op == "*" {
        return Int64(op1)! * Int64(op2)!
    } else if op == "/" {
        return Int64(op1)! / Int64(op2)!
    }
    return 0
}