[Programmers] 2020 카카오 인턴십 - 수식 최대화 (Swift)

문제 : 

https://programmers.co.kr/learn/courses/30/lessons/67257

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

 

Step 1. 문제 이해하기

• 숫자(999 이하)와 연산자('+', '-', '*')를 띄어쓰기 없이 포함한 문자열 변수 expression이 존재
• 문자열의 총길이는 3 이상 100 이하
• 연산자 우선순위를 임의로 설정하여 나온 우승상금(결괏값)의 절댓값이 가장 큰 값을 출력

 

Step 2. 문제 풀이 생각하기

1. 연산자 우선순위 조합을 어떻게 구현할 것인지 먼저 생각했습니다. 연산자 우선순위 조합은 총 6가지이기 때문에 해시 테이블로 생성해서 충분히 구현할 수 있을 것이라고 판단했습니다. (처음에는 '*' 이후에 '+', '-'의 순서는 상관없다고 생각했지만 상관있습니다.)
2. 문자열 슬라이싱에 대해서 생각했습니다. 문자열에 띄어쓰기가 없기 때문에 문자 하나씩 isNumber 함수를 이용해서 숫자는 숫자대로 연산자는 연산자대로 문자열 배열에 슬라이싱해서 값을 넣었습니다.
3. 해시에 저장된 연산자 우선순위에 따라 계산이 될 때마다 두 번째 피연산자에 연산한 결괏값을 넣고 첫 피연산자와 연산자를 지웁니다. 이 과정을 반복해야 하기 때문에 문자열 배열을 복사한 다음 진행합니다.
4. 모든 연산이 끝난 후에는 복사한 배열에 결괏값 하나만 남아 있기 때문에 결괏값의 절댓값과 ans를 비교해서 큰 값을 저장합니다.
5. 3 ~ 4 과정 반복

 

'*' > '+' > '-' 순서 예시

 

Step 3. 차근차근 구현하기

import Foundation

func solution(_ expression:String) -> Int64 {
    var ans = 0
    // 연산자 우선순위 조합으로 나올 수 있는 모든 경우의 수를 해시 테이블로 저장
    let ht = [0 : ["*", "+", "-"], 1 : ["*", "-", "+"], 2 : ["+", "*", "-"], 3 : ["+", "-", "*"], 4 : ["-", "+", "*"], 5 : ["-", "*", "+"]]
    var expressionArr = [String]()
    var tmpValue = ""
    // 연산자와 피연산자를 구분해서 expressionArr에 저장
    for (idx, value) in expression.enumerated() {
        if value.isNumber {
            tmpValue += String(value)
            if idx == expression.count - 1 {
                expressionArr.append(tmpValue)
            }
        }
        else {
            expressionArr.append(tmpValue)
            expressionArr.append(String(value))
            tmpValue = ""
        }
    }
    
    // 전체 경우의 수 실행하는 for문
    for key in 0..<6 {
        var expressionArrCopy = expressionArr
        for operIdx in 0..<3 {
            var idx = 0
            for value in expressionArrCopy {
                // 연산자를 찾으면 해당 연산자가 포함된 식의 2번째 피연산자에 값을 갱신
                if ht[key]![operIdx] == value {
                    if value == "*" {
                        expressionArrCopy[idx + 1] = String(Int(expressionArrCopy[idx - 1])! * Int(expressionArrCopy[idx + 1])!)
                    }
                    else if value == "+" {
                        expressionArrCopy[idx + 1] = String(Int(expressionArrCopy[idx - 1])! + Int(expressionArrCopy[idx + 1])!)
                    }
                    else if value == "-" {
                        expressionArrCopy[idx + 1] = String(Int(expressionArrCopy[idx - 1])! - Int(expressionArrCopy[idx + 1])!)
                    }
                    // 첫 번째 피연산자와 연산자를 remove하고 idx도 -2해주기
                    expressionArrCopy.remove(at: idx - 1)
                    expressionArrCopy.remove(at: idx - 1)
                    idx -= 2
                }
                idx += 1
            }
        }
        // 5가지 경우의 수를 모두 탐색하면서 가장 큰 절대 값을 ans에 저장
        ans = max(ans, abs(Int(expressionArrCopy[0])!))
    }
    return Int64(ans)
}

 

Step 4. 피드백

• 해시 테이블을 사용해야 하는 것은 알았지만, 연산한 결과 값을 어디에 어떻게 저장할 지에 대한 생각하는데 시간을 많이 소비했던 것 같습니다.
• Swift에서 문자열을 슬라이싱하는 것이 파이썬에서 처럼 String[0]의 형태로 사용할 수 없기 때문에 이 부분에서 좀 막혔었고 copy를 처음에 어떻게 하는지 몰랐는데 '='로 deepCopy 할 수 있다는 것을 알았습니다.