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

요구능력 : 재귀함수

 

코드설명 : 

 

내가 처음에 시간초과가 났던 코드는 문자열에 모든 연산자를 집어넣고 그 연산자를 백트래킹하면서 모든 경우의수를 다 세보는 코드다.

처음에는 연산자끼워넣기랑 똑같이 풀었다.

그러다 블로그를 서칭하던중에 내가 쓴 코드가 범위를 한참초과해서 시간초과가 난다는것을 알게되었다.

수의 개수는 최대 11개까지 들어온다.

그럼 연산자의 개수는 한번의 연산에 최대 10개를 쓸 수 있다.

그리고 연산자는 최대 4N개가 주어지니까

44개에서 10개를 뽑으면 44C10이 되고, 이걸 정렬하는 데는 연산자의 개수만큼 걸리니

44C10 * 10이 나온다. 그럼 시간초과가 나게된다.

(다른분들은 다 11이라고 적으셧던데 저는 10이라고 생각해서 10으로 적었습니다. 틀렸다면 이유좀 댓글로 부탁드립니다..)

let n = Int(String(readLine()!))!
let arr = readLine()!.split(separator: " ").map{Int(String($0))!}
var operandArr = readLine()!.split(separator: " ").map{Int(String($0))!}
var operArr = [Character]()
var visited = Array(repeating: false, count: 100)
var result = arr[0]
var resultMax = -1000000001
var resultMin = Int.max
var oper = [Character]()
while true{
    if operandArr[0] == 0 && operandArr[1] == 0 && operandArr[2] == 0 && operandArr[3] == 0{
        break
    }

    if operandArr[0] >= 1{
        operandArr[0] -= 1
        operArr.append("+")
    }
    if operandArr[1] >= 1{
        operandArr[1] -= 1
        operArr.append("-")
    }
    if operandArr[2] >= 1{
        operandArr[2] -= 1
        operArr.append("*")
    }
    if operandArr[3] >= 1{
        operandArr[3] -= 1
        operArr.append("/")
    }
}
var count = 0
func dfs(_ depth: Int){
    if depth == n - 1{
        print(oper)
        for i in 0..<oper.count{
            if oper[i] == "+"{
                result += arr[i + 1]
            }
            if oper[i] == "-"{
                result -= arr[i + 1]
            }
            if oper[i] == "*"{
                result *= arr[i + 1]
            }
            if oper[i] == "/"{
                result /= arr[i + 1]
            }
        }
        resultMin = min(resultMin, result)
        resultMax = max(resultMax, result)
        result = arr[0]
        count += 1
        return
    }
    for i in 0..<operArr.count{
        if !visited[i]{
            visited[i] = true
            oper.append(operArr[i])

            dfs(depth + 1)
            visited[i] = false
            oper.removeLast()
        }
    }
}

dfs(0)
print(count)
print(resultMax)
print(resultMin)

출력결과 총 30개가 나온 모습이다.

아래를 보면 중복되서 나오는 것들이 몇개 보인다.

내가 문자열에 다 저장해놓고 순열을 돌렸으니 당연한 결과이다.

이 중복을 해결하면 문제가 해결되는 것이다.

그렇다면 어떤 방법이 있을까? 바로 재귀이다.

재귀로 풀게되면 계속해서 리턴해서 내려가면서 문제를 풀어나가기 때문에 중복되는 경우가 나오지 않을것이다.

 

개수차이가 궁금하다면 아래 정답코드에서 주석처리한 부분을 주석제거하고 위의 출력결과와 같은 예제를 아래 정답코드에 넣고 돌려보길 권장한다.

 

결론적으로 중복을 없애기위해서 재귀를 사용한거라고 보면된다.

 

후기 :  이전에 풀었던 연산자끼워넣기 처럼 풀다가 이문제에 시간을 너무쏟았다.

재귀와 백트래킹에 대한 완벽한 이해를 가져야 풀수있는 문제같았다.

다른 블로그들 보면서 참고하면서 풀어봤다.

let n = Int(String(readLine()!))!
let arr = readLine()!.split(separator: " ").map{Int(String($0))!}
var operandArr = readLine()!.split(separator: " ").map{Int(String($0))!}
var resultMax = -1000000001
var resultMin = Int.max

//var count = 0
func dfs(_ i: Int, _ res: Int, _ add: Int, _ sub: Int, _ mul: Int, _ div: Int){
//    count += 1
    if i == n {
        resultMax = max(resultMax, res)
        resultMin = min(resultMin, res)
        return
    }
    if add != 0{
        dfs(i + 1, res + arr[i], add - 1, sub, mul, div)
    }
    if sub != 0{
        dfs(i + 1, res - arr[i], add, sub - 1, mul, div)
    }
    if mul != 0{
        dfs(i + 1, res * arr[i], add, sub, mul - 1, div)
    }
    if div != 0{
        dfs(i + 1, res / arr[i], add, sub, mul, div - 1)
    }
}
dfs(1, arr[0], operandArr[0], operandArr[1], operandArr[2], operandArr[3])
print(resultMax)
print(resultMin)
//print(count)