프로그래머스 - [카카오 인턴] 수식 최대화Swift (DFS, 구현)

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

 

---

풀이 및 소스코드

원래의 우선순위는 당연히 *, / -> -+이다 식은 그대로 두고, 이 우선순위를 바꿔가며 계산을 해나가는데

+를 먼저하냐, *를 먼저하냐, -를 먼저하냐의 문제.

DFS까진 사용할 필요 없지만 DFS으로 *-+의 순열을 만들어서 순열이 만들어 지면 앞에있는 순서대로 우선순위를 정해 계산해 나갔다.

oprator는 3종류다 따라서 3번 반복하게 될거고, op의 순서마다 배열에서 op가 사라질 때 까지 반복해나간다.

idx 에 op가 위치한다면

(idx-1...idx+1) 의 위치를 (idx-1 op idx+1)로 변경해주었다.

exp.replaceSubrange(i-1...i+1, with: [String(before + after)])

import Foundation
//숫자와 3가지의 연산문자만으로 이루어진 수식
//연산자의 우선순위를 재정의하여 만들 수 있는 가장 큰 숫자를 제출
func solution(_ expression:String) -> Int64 {
    //수식을 숫자와, 연산자로 나눔
    var tmp = ""
    var operlands = ["*", "+", "-"]
    var exparr = [String]()
    var max: Int64 = 0
    
    for char in expression{
        if "1234567890".contains(char){
            tmp += String(char)
        }else{
            exparr.append(tmp)
            tmp = ""
            exparr.append(String(char))
        }
    }
    exparr.append(tmp)
    
    //dfs로 순열을 만들어서.. 사실 쓸필요 없는데 연습겸
    var string = ""
    var visited = [Bool](repeating: false, count: 3)
    
    func dfs(){
        if string.count == 3{
            //순열이 만들어지면 해당 우선순위를 대입한 계산을 하고 결과값을 max로 저장
            let result = (calculator(exparr, string))
            if result > max{
                max = result
            }
            return
        }
        
        for i in 0..<3{
            if !visited[i]{
                visited[i] = true
                string += operlands[i]
                dfs()
                string.removeLast()
                visited[i] = false
            }
        }
    }
    
    
    dfs()

    return max
}

//우선순위대로 계산을 하는 식
func calculator(_ expression: [String], _ priority: String) -> Int64{
    var result: Int64 = 0
    var exp = expression
    
    //op는 3개가 들어오므로 3번 반복
    for op in priority{
        var i = 0
        while exp.contains(String(op)){//배열 내에 op가 없을 때까지 반복
            if let _ = Int64(exp[i]){}else{
                let before = Int64(exp[i-1])!
                let after = Int64(exp[i+1])!
                
                if exp[i] == String(op) && exp[i] == "*"{// i-1부터 i+1의 원소를 해상 op의 계산 결과로 바꿈, 처음부터 시작
                    exp.replaceSubrange(i-1...i+1, with: [String(before * after)])
                    i = 0
                }
                if exp[i] == String(op) && exp[i] == "-"{
                    exp.replaceSubrange(i-1...i+1, with: [String(before - after)])
                    i = 0
                }
                if exp[i] == String(op) && exp[i] == "+"{
                    exp.replaceSubrange(i-1...i+1, with: [String(before + after)])
                    i = 0
                }
            }
            i += 1
        }
    }
   
    return Int64(abs(Int(exp[0]) ?? 0))
}