[Swift][BruteForce] 백준 14888번 (연산자 끼워넣기)

요구능력 : 백트래킹과 문자열

 

코드설명 : 

 

연산자를 배열에 다 넣어준다.

var temp = [Character]()
var operArr = operandArr
for i in 0..<4{
    while operArr[i] >= 1 {
        if i == 0{
            temp.append("+")
            operArr[i] -= 1
        }else if i == 1{
            temp.append("-")
            operArr[i] -= 1
        }else if i == 2{
            temp.append("*")
            operArr[i] -= 1
        }else if i == 3{
            temp.append("/")
            operArr[i] -= 1
        }
    }
}

 

연산자를 백트래킹 하면서 경우의수를 모두 계산해준다.

func dfs(_ depth: Int){
    var p = 1
    var result = arr[0]
    if depth == temp.count{
        for i in resultArr{
            if i == "+"{
                result += arr[p]
                p = p + 1
            }else if i == "-"{
                result -= arr[p]
                p = p + 1
            }else if i == "*"{
                result *= arr[p]
                p = p + 1
            }else if i == "/"{
                result /= arr[p]
                p = p + 1
            }
        }

        maxResult = max(result, maxResult)
        minResult = min(result, minResult)
        return
    }
    for i in 0..<temp.count{
        if !visited[i] {
            visited[i] = true
            resultArr.append(temp[i])
            dfs(depth + 1)
            visited[i] = false
            resultArr.removeLast()
        }
    }

}

 

후기 :  처음 문제를 보면 어려워보일 수 있지만 풀어나가면 쉬운문제

나는 처음에 수를 백트래킹하다가 어딘가 이상해서 연산자를 백트래킹하는 걸로 갈아탔다.

let n = Int(String(readLine()!))!
let arr = readLine()!.split(separator: " ").map{Int(String($0))!}
let operandArr = readLine()!.split(separator: " ").map{Int(String($0))!}
var resultArr = [Character]()
var visited = Array(repeating: false, count: n + 1)
var maxResult = -999999999
var minResult = Int.max

var temp = [Character]()
var operArr = operandArr
for i in 0..<4{
    while operArr[i] >= 1 {
        if i == 0{
            temp.append("+")
            operArr[i] -= 1
        }else if i == 1{
            temp.append("-")
            operArr[i] -= 1
        }else if i == 2{
            temp.append("*")
            operArr[i] -= 1
        }else if i == 3{
            temp.append("/")
            operArr[i] -= 1
        }
    }
}


func dfs(_ depth: Int){
    var p = 1
    var result = arr[0]
    if depth == temp.count{
        for i in resultArr{
            if i == "+"{
                result += arr[p]
                p = p + 1
            }else if i == "-"{
                result -= arr[p]
                p = p + 1
            }else if i == "*"{
                result *= arr[p]
                p = p + 1
            }else if i == "/"{
                result /= arr[p]
                p = p + 1
            }
        }

        maxResult = max(result, maxResult)
        minResult = min(result, minResult)
        return
    }
    for i in 0..<temp.count{
        if !visited[i] {
            visited[i] = true
            resultArr.append(temp[i])
            dfs(depth + 1)
            visited[i] = false
            resultArr.removeLast()
        }
    }

}
dfs(0)
print(maxResult)
print(minResult)