[Algorithm] 백준 - 16638번 괄호 추가하기2 (Swift)

🧐 문제

https://www.acmicpc.net/problem/16638

✨ 풀이

괄호, 곱하기, 그외 연산자 순으로 연산을 진행하면 되겠다라고 생각했다. 그리고 괄호는 중복되면 안되기 때문에 오른쪽부터 괄호를 씌우게 하지만 이전에 괄호가 있다면 무조건 한칸 건너띄게 괄호를 넣을 수 있게 했다.

let n = Int(readLine()!)!
let math = Array(readLine()!).map { String($0) }

var cap = Array(repeating: false, count: n)

/// ["숫자", "부호", "숫자"] 연산
func operation(_ array: [String]) -> String {
    let left = Int(array[0])!
    let right = Int(array[2])!

    switch array[1] {
    case "*": return String(left * right)
    case "+": return String(left + right)
    case "-": return String(left - right)
    default: return "error"
    }
}

/// 괄호 -> 곱셈 -> 나머지 순서대로 연산
func calculate() -> Int {
    var temp1 = [math[0]]

    /// 괄호
    for i in stride(from: 1, to: n, by: 2) {
        if cap[i-1] {
            let last = temp1.removeLast()
            temp1.append(operation([last] + Array(math[i...i+1])))
        } else {
            temp1.append(math[i])
            temp1.append(math[i+1])
        }
    }

    var temp2 = [temp1[0]]
    
    /// 곱셈
    for i in stride(from: 1, to: temp1.count, by: 2) {
        if temp1[i] == "*" {
            let last = temp2.removeLast()
            temp2.append(operation([last] + Array(temp1[i...i+1])))
        } else {
            temp2.append(temp1[i])
            temp2.append(temp1[i+1])
        }
    }

    var temp3 = [temp2[0]]

    /// 나머지 무조건 연산
    for i in stride(from: 1, to: temp2.count, by: 2) {
        let last = temp3.removeLast()
        temp3.append(operation([last] + Array(temp2[i...i+1])))
    }

    return Int(temp3[0])!
}

var answer = calculate()

/// 가능한 모든 괄호에서 계산, 곱셈에서는 괄호를 씌우지 않음
func dfs(index: Int) {
    for i in stride(from: index, to: n-1, by: 2) {
        if !cap[max(i-2, 0)] && math[i] != "*" {
            cap[i] = true
            answer = max(answer, calculate())
            dfs(index: i+2)
            cap[i] = false
        }
    }
}

dfs(index: 0)

print(answer)

🧙 결과

🎉~ 아주 효과적으로 통과한 것 같다.