코딩테스트 연습 - 수식 최대화

문제 풀이 아이디어

문제를 보면 상당히 복잡한 것 같지만 단계를 쪼개서 보면 각각의 해결 방안은 생각보다 쉽습니다. 총 3파트로 나누어서 문제를 해결해보도록 하겠습니다.

String으로 주어진 식을 연산자와 피연산자로 분리하기

주어진 식을 연산자와 피연산자로 구분합니다. 연산자의 경우 string의 길이가 1이기 때문에 관계 없지만 피연산자 (= 숫자)의 경우 길이가 1이상인 경우도 있으므로 temp를 활용해서 연산자가 나올 때까지 나온 숫자를 모아서 한번에 Int로 변환합니다.

연산자들의 우선순위 case 구하기

연산자들의 우선순위 case를 구하기 위해서 순열을 사용합니다.

우선순위 고려해서 연산하기

다른 분들의 풀이를 보면 연산자와 피연산자를 하나의 배열에 넣고 연산하는 분이 많던데 저는 연산자와 피연산자의 배열을 분리해서 사용했습니다.

각각 다른 배열에서 i번째 피연산자를 통해서 연산되는 피연산자는 i번째와 i + 1번째 피연산자입니다. 그리고 연산한 결과는 i번째 피연산자에 덮어 씌우고 i + 1 번째 피연산자와 i번째 피연산자는 제거합니다.

위 연산을 연산자 배열이 빌 때까지 실행하면 연산의 결과가 나옵니다.

그런데 우선순위를 고려해야 하므로 우선순위 배열에서 앞에 있는 연산자부터 사용해서 연산을 하면 답을 얻을 수 있습니다.

코드

// swift로 순열 구현
func permutation(of: [String]) -> [[String]] {
    var result = [[String]]()
    var visited = Array(repeating: false, count: of.count)
    
    func dfs(_ now: [String]) {
        if now.count == of.count {
            result.append(now)
            return
        }
        
        for i in 0..<of.count {
            if !visited[i] {
                visited[i] = true
                dfs(now + [of[i]])
                visited[i] = false
            }
        }
    }

    dfs([])
    
    return result
}

// 연산 함수
func operate(_ lhs: Int, _ rhs: Int, _ oper: String) -> Int {
    switch oper {
    case "+": return lhs + rhs
    case "-": return lhs - rhs
    case "*": return lhs * rhs
    default: return 0
    }
}

func solution(_ expression:String) -> Int64 {
    
    // 문자열을 피연산자와 연산자로 분리하기
    var operands = [Int]()
    var operators = [String]()
    let expression = expression.map { $0 }
    var i = 0
    var temp = ""
    
    while i < expression.count {
        // 숫자면 temp에 추가
        if expression[i].isNumber {
            temp += String(expression[i])
        // 숫자가 아니면 temp를 Int로 변환해서 피연산자에 추가하고 연산자도 배열에 추가
        } else {
            operands.append(Int(temp)!)
            temp = ""
            operators.append(String(expression[i]))
        }
        i += 1
    }
    
    // 반복문을 돌고 마지막 temp 피연산자 배열에 추가
    operands.append(Int(temp)!)
    
    // 연산자의 우선순위 순서대로 연산하는 함수
    func calculate(_ priority: [String]) -> Int {
        var operands = operands
        var operators = operators
        // 연산자 우선순위 반복문
        for p in priority {
            // 해당 연산자가 operators 배열에 있을 때까지 반복
            while let i = operators.firstIndex(of: p) {
                let result = operate(operands[i], operands[i + 1], operators[i])
                // 연산한 결과를 i 자리에 넣고
                operands[i] = result
                // i + 1과 연산자는 제거
                operands.remove(at: i + 1)
                operators.remove(at: i)
            }
        }
        
        // 마지막 남은 1개의 숫자의 절대값을 리턴
        return abs(operands[0])
    }
    
    // 연산 결과들을 저장하는 배열
    var results = [Int]()
    
    // 연산자의 우선순위 case 6가지 구하기 (by 순열)
    let types = ["+", "-", "*"]
    let priorities = permutation(of: types)
    
    // 우선순위 케이스 별로 연산해서
    for priority in priorities {
        results.append(calculate(priority))
    }
    
    // 최댓값을 리턴한다.
    return Int64(results.max()!)
}