[백준] 14888 - Swift

https://www.acmicpc.net/problem/14888
문제 링크

시간초과 코드

let num = Int(readLine()!)!
let nums = readLine()!.split(separator: " ").map{Int($0)!}
let arr = readLine()!.split(separator: " ").map{Int($0)!}
var pattern = [String]()
var answers = [[String]]()

for (index, value) in arr.enumerated(){
    if value > 0 {
        if index == 0 {
            for _ in 0..<value {
                pattern.append("+")
            }
        } else if index == 1 {
            for _ in 0..<value {
                pattern.append("-")
            }
        } else if index == 2 {
            for _ in 0..<value {
                pattern.append("*")
            }
        } else if index == 3 {
            for _ in 0..<value {
                pattern.append("/")
            }
        }
    }
}

var max = -1100
var min = 1100
var visited = Array(repeating: false, count: pattern.count)

func dfs(_ index: Int, _ length: Int, _ stack: [String]) {
    if length == pattern.count {
        var sum = nums.first!
        var next = 1
        for i in stack {
            if i == "+" {
                sum += nums[next]
                next += 1
            } else if i == "-" {
                sum -= nums[next]
                next += 1
            } else if i == "*" {
                sum *= nums[next]
                next += 1
            } else if i == "/" {
                sum /= nums[next]
                next += 1
            }
        }
        if max < sum {
            max = sum
        }
        if min > sum {
            min = sum
        }
        return
    }
    
    for i in 0..<pattern.count {
        if !visited[i] {
            visited[i] = true
            dfs(i, length+1, stack + [pattern[i]])
            visited[i] = false
        }
    }
}

dfs(0,0,[])

print(max)
print(min)

모든 연산자 조합을 다 구해서 모든 값을 구하고 max, min을 구했더니 시간초과가 났다..

코드

let num = Int(readLine()!)!
let nums = readLine()!.split(separator: " ").map{Int($0)!}
var arr = readLine()!.split(separator: " ").map{Int($0)!}

var maxValue = Int.min
var minValue = Int.max

func dfs(_ answer: Int, _ length: Int) {
    if length == num {
        maxValue = max(answer, maxValue)
        minValue = min(answer, minValue)
        return
    }
    for i in 0..<4 {
        if arr[i] < 1 {
            continue
        }
        arr[i] -= 1
        // 모든 경우의 수 탐색
        switch i {
        case 0:
            dfs(answer+nums[length], length+1)
        case 1:
            dfs(answer-nums[length], length+1)
        case 2:
            dfs(answer*nums[length], length+1)
        case 3:
            dfs(answer/nums[length], length+1)
        default:
            break
        }
        arr[i] += 1
    }
}


dfs(nums[0], 1)

print(maxValue)
print(minValue)

회고

• 시간 초과를 생각해야겠다
• 똑같은 완전 탐색인데 과정을 달리하여 시간초과를 벗어나는 것이 신기했다
• 더 풀어봐야겠다