[Swift 알고리즘] 프로그래머스(Lv.2) - 수식 최대화 / 2020 카카오 인턴십

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "프로그래머스(Lv.2) - 수식 최대화" 문제를 풀었습니다.

 

---

 

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

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

 

---

풀이

이번 문제는 문자열 처리와 완전 탐색 문제입니다.

문제를 풀다보니 카카오는 이렇게 문자열 처리를 다른 알고리즘과 합쳐서 출시를 하더라고요.

 

+, -, *이 포함된 수식이 주어질 때 결과의 절대값 중 가장 큰 값을 return 하면 됩니다.

 

1. 연산자의 우선순위를 정의합니다.

이번 문제는 6가지 종류 밖에 안 되기 때문에 직접 입력하여 상수로 초기화 하였습니다.

이렇게 가짓수가 적을 때는 직접 초기화하는 것도 가독성 면에서 좋습니다.

 

2. input 문자열을 숫자와 연산자로 나눕니다.

저는 문자 하나하나 보며 연산자와 숫자를 나누어 주었습니다.

연산자도 포함되어 있기 때문에 String 배열로 구현하였습니다.

 

3. 1번에서 정의한 우선순위에 따라 결과값을 구합니다.

이 단계부터는 완전 탐색 구현입니다. 하나하나 반복하며 결과를 구합니다.

우선순위가 높은 연산자를 계산한 수식을 배열에 다시 담습니다.

그후 다음으로 우선순위가 높은 연산자를 계산한 수식을 배열에 담습니다.

마지막으로 우선순위가 가장 낮은 연산자를 계산한 결과값을 배열에 담습니다.

 

이때, 배열에 담긴 item의 개수가 1개라면 break합니다.

item이 1개라는 것은 연산이 끝난 결과가 담겼다는 의미이기 때문입니다.

 

+, -, *만 존재하기 때문에 시간복잡도를 생각하지 않고 구현이 가능합니다.

참 감사한 문제 같습니다.

 

---

전체 코드

import Foundation

func splitExpression(_ expression: String) -> [String] {
    var result: [String] = []
    var str = ""
    for ch in expression {
        let s = String(ch)
        switch s {
            case "-", "+", "*":
                result.append(str)
                result.append(s)
                str = ""
            default:
                str += s
                break
        }
    }
    
    result.append(str)
    return result
}

func solution(_ expression:String) -> Int64 {
    let expressionsArr: [[String]] = [["+", "-", "*"], ["+", "*", "-"],
                                      ["-", "+", "*"], ["-", "*", "+"],
                                      ["*", "+", "-"], ["*", "-", "+"]]
    
    let arr = splitExpression(expression)
    var maxResult: Int64 = Int64.min
    for expressions in expressionsArr { //6회 반복
        var calArr: [String] = []
        var tempArr = arr
        for exp in expressions { //3회 반복
            calArr = []
            if tempArr.contains(exp) {
                for item in tempArr {
                    if calArr.count > 0 && calArr.last! == exp {
                        let _ = calArr.popLast()!
                        let num = calArr.popLast()!
                        
                        switch exp {
                            case "+": calArr.append(String(Int64(num)! + Int64(item)!))
                            case "-": calArr.append(String(Int64(num)! - Int64(item)!))
                            case "*": calArr.append(String(Int64(num)! * Int64(item)!))
                            default: break
                        }
                    } else {
                        calArr.append(item)
                    }
                }
            }
            tempArr = calArr
            
            if tempArr.count == 1 {
                break
            }
        }
                
        if !tempArr.isEmpty {
            let num = Int64(abs(Int64(tempArr[0])!))
            maxResult = max(maxResult, num)
        }
    }
    
    return maxResult
}

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.