수식 최대화

LEEHAKJIN-VV·2022년 6월 10일
algorithmprogrammersswift문자열
0

프로그래머스

목록 보기
22/37

출처: 프로그래머스 코딩 테스트 연습

문제 설명

IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다.
이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 같은 방식으로 결정하려고 합니다.
해커톤 대회에 참가하는 모든 참가자들에게는 숫자들과 3가지의 연산문자(+, -, *) 만으로 이루어진 연산 수식이 전달되며, 참가자의 미션은 전달받은 수식에 포함된 연산자의 우선순위를 자유롭게 재정의하여 만들 수 있는 가장 큰 숫자를 제출하는 것입니다.
단, 연산자의 우선순위를 새로 정의할 때, 같은 순위의 연산자는 없어야 합니다. 즉, + > - > * 또는 - > * > + 등과 같이 연산자 우선순위를 정의할 수 있으나 +,* > - 또는 * > +,-처럼 2개 이상의 연산자가 동일한 순위를 가지도록 연산자 우선순위를 정의할 수는 없습니다. 수식에 포함된 연산자가 2개라면 정의할 수 있는 연산자 우선순위 조합은 2! = 2가지이며, 연산자가 3개라면 3! = 6가지 조합이 가능합니다.
만약 계산된 결과가 음수라면 해당 숫자의 절댓값으로 변환하여 제출하며 제출한 숫자가 가장 큰 참가자를 우승자로 선정하며, 우승자가 제출한 숫자를 우승상금으로 지급하게 됩니다.

예를 들어, 참가자 중 네오가 아래와 같은 수식을 전달받았다고 가정합니다.

"100-200*300-500+20"

일반적으로 수학 및 전산학에서 약속된 연산자 우선순위에 따르면 더하기와 빼기는 서로 동등하며 곱하기는 더하기, 빼기에 비해 우선순위가 높아 * > +,- 로 우선순위가 정의되어 있습니다.
대회 규칙에 따라 + > - > * 또는 - > * > + 등과 같이 연산자 우선순위를 정의할 수 있으나 +,* > - 또는 * > +,- 처럼 2개 이상의 연산자가 동일한 순위를 가지도록 연산자 우선순위를 정의할 수는 없습니다.
수식에 연산자가 3개 주어졌으므로 가능한 연산자 우선순위 조합은 3! = 6가지이며, 그 중 + > - > * 로 연산자 우선순위를 정한다면 결괏값은 22,000원이 됩니다.
반면에 * > + > - 로 연산자 우선순위를 정한다면 수식의 결괏값은 -60,420 이지만, 규칙에 따라 우승 시 상금은 절댓값인 60,420원이 됩니다.

참가자에게 주어진 연산 수식이 담긴 문자열 expression이 매개변수로 주어질 때, 우승 시 받을 수 있는 가장 큰 상금 금액을 return 하도록 solution 함수를 완성해주세요.

제한 사항

  • expression은 길이가 3 이상 100 이하인 문자열입니다.
  • expression은 공백문자, 괄호문자 없이 오로지 숫자와 3가지의 연산자(+, -, *) 만으로 이루어진 올바른 중위표기법(연산의 두 대상 사이에 연산기호를 사용하는 방식)으로 표현된 연산식입니다. 잘못된 연산식은 입력으로 주어지지 않습니다.
    • 즉, "402+-561*"처럼 잘못된 수식은 올바른 중위표기법이 아니므로 주어지지 않습니다.
  • expression의 피연산자(operand)는 0 이상 999 이하의 숫자입니다.
    • 즉, "100-2145*458+12"처럼 999를 초과하는 피연산자가 포함된 수식은 입력으로 주어지지 않습니다.
    • "-56+100"처럼 피연산자가 음수인 수식도 입력으로 주어지지 않습니다.
  • expression은 적어도 1개 이상의 연산자를 포함하고 있습니다.
  • 연산자 우선순위를 어떻게 적용하더라도, expression의 중간 계산값과 최종 결괏값은 절댓값이 263 - 1 이하가 되도록 입력이 주어집니다.
  • 같은 연산자끼리는 앞에 있는 것의 우선순위가 더 높습니다.

입출력 예

expressionresult
"100-200*300-500+20"60420
"506-32"300

입출력 예 설명

입출력 예 #1
* > + > - 로 연산자 우선순위를 정했을 때, 가장 큰 절댓값을 얻을 수 있습니다.
연산 순서는 아래와 같습니다.
100-200*300-500+20

= 100-(200*300)-500+20
= 100-60000-(500+20)
= (100-60000)-520
= (-59900-520)
= -60420
따라서, 우승 시 받을 수 있는 상금은 |-60420| = 60420 입니다.

입출력 예 #2
- > * 로 연산자 우선순위를 정했을 때, 가장 큰 절댓값을 얻을 수 있습니다.
연산 순서는 아래와 같습니다.(expression에서 + 연산자는 나타나지 않았으므로, 고려할 필요가 없습니다.)
50*6-3*2
= 50*(6-3)*2
= (50*3)*2
= 150*2
= 300
따라서, 우승 시 받을 수 있는 상금은 300 입니다.

내가 제출한 코드

import Foundation

func solution(_ expression:String) -> Int64 {
    var operationResult: Int64 = -1 // 우승시 상금
    let OPERAND: [[String]] = [["*","+","-"],["*","-","+"],["-","*","+"],
                                      ["-","+","*"],["+","*","-"],["+","-","*"]] // 연산자 우선순위 6가지 조합
  
    for operandPriority in OPERAND { // 연산자 우선순위 6가지를 검사
        var expressionArray: [String] = sliceExpression(expression) // 문자열 배열
        for i in 0..<3 { // 제일 우선순위가 높은 연산자 부터 우선 계산
            let operand = operandPriority[i] // i번째에 해당하는 연산자 꺼냄
            var index = 0
            while index < expressionArray.count{ // 배열을 끝까지 읽을 때까지
                if expressionArray[index] == operand { // 읽은 element가 계산해야 하는 경우
                    // 중위 표기식이므로 [연산자 피연산자 연산자]의 순서를 무조건 지킴 -> forced unwrapping 사용
                    let result = calOperation(Int(expressionArray[index - 1])!, Int(expressionArray[index + 1])!, operand)
                    expressionArray.replaceSubrange((index - 1)...(index + 1), with: repeatElement(String(result), count:1))
                    continue // 배열의 (index-1,index,index+1)대신 새로운 연산값을 할당하였으므로 index를 전진하지 않아도 다음 index를 가르킴
                }
                index += 1
            }
        }
        let number = Int64(expressionArray[0]) ?? -2 // nil 병합연산자
        operationResult = (operationResult < abs(number)) ? abs(number) : operationResult // 최대 우승상금 결정
    }
    
    return operationResult
}

// 표현식을 배열로 만들기
func sliceExpression(_ strings: String) -> [String] {
    var tmp: String = ""
    var expressionArray: [String] = []
    
    for str in strings.map {String($0) } {
        if Character(str).isNumber {
            tmp += str
        } else {
            expressionArray.append(contentsOf: [tmp,str])
            tmp = ""
        }
    }
    expressionArray.append(tmp)
    return expressionArray
}

func calOperation(_ num1: Int, _ num2: Int, _ op: String) -> Int {
    if op == "*" {
        return num1 * num2
    } else if op == "-" {
        return num1 - num2
    } else {
        return num1 + num2
    }
}

코드 설명

문제는 단순 문자열 처리로 해결한다. 진행 과정을 소개한다.

  1. 연산자 우선순위에 따라 6개의 조합을 만든다.
  2. 각 조합에 따라 받을 수 있는 상금을 구함
  3. 최대 상금을 계산

이 풀이의 핵심은 수식이 담긴 문자열 expression가 중위 표기법이라는 것이다.

그러면 각 과정을 세부적으로 살펴본다.

연산자의 6개 조합을 정의하였다. 1개의 배열 ["*","+","-"]을 선언하여 반복문으로도 정의하는 방법도 있다.

let OPERAND: [[String]] = [["*","+","-"],["*","-","+"],["-","*","+"],
                                      ["-","+","*"],["+","*","-"],["+","-","*"]] // 연산자 우선순위 6가지 조합

다음으로 연산을 수행하기 위해 수식이 담긴 문자열을 연산자와 피연산자로 구분하여 문자열 배열을 만드는 코드다.

var expressionArray: [String] = sliceExpression(expression) // 문자열 배열

func sliceExpression(_ strings: String) -> [String] {
    var tmp: String = ""
    var expressionArray: [String] = []
    
    for str in strings.map {String($0) } {
        if Character(str).isNumber {
            tmp += str
        } else {
            expressionArray.append(contentsOf: [tmp,str])
            tmp = ""
        }
    }
    expressionArray.append(tmp)
    return expressionArray
    // 	["100", "-", "200", "*", "300", "-", "500", "+", "20"]
}

우선 문자열 배열을 만든 이유는 연산을 수행하기 위해 계속 문자열에 접근해야 하는 데 swift에서 문자열 처리는 다른 언어보다 복잡하다고 생각하기 때문에 조작하기 더 쉬운 방법인 배열로 변환하였다.

다음으로 연산을 계산하는 코드다.

for i in 0..<3 { // 제일 우선순위가 높은 연산자 부터 우선 계산
    let operand = operandPriority[i] // i번째에 해당하는 연산자 꺼냄
    var index = 0
    while index < expressionArray.count{ // 배열을 끝까지 읽을 때까지
        if expressionArray[index] == operand { // 읽은 element가 계산해야 하는 경우
            // 중위 표기식이므로 [연산자 피연산자 연산자]의 순서를 무조건 지킴 -> forced unwrapping 사용
            let result = calOperation(Int(expressionArray[index - 1])!, Int(expressionArray[index + 1])!, operand)
            expressionArray.replaceSubrange((index - 1)...(index + 1), with: repeatElement(String(result), count:1))
            continue // 배열의 (index-1,index,index+1)대신 새로운 연산값을 할당하였으므로 index를 전진하지 않아도 다음 index를 가르킴
        }
        index += 1
    }
}

연산에 수행할 연산자의 우선순위가 다르다. 그러므로 수식에서 한 번에 모든 연산자(*,+,-)를 계산하는 것이 아닌 3번에 걸쳐, 오직 1개의 연산자만 연산하는 방법을 사용한다. operand 프로퍼티에는 이번에 계산에 사용할 연산자가 할당된다.

연산자가 할당되었다면 수식에서 연산을 수행할 차례이다. 앞서 말했듯이 이번 풀이에서 중요한 점은 수식이 중위 표기법이라는 점이다. 중위 표기법은 (피연산자-연산자-피연산자)순으로 수식이 구성된다. index를 증가시켜 수식에서 연산자를 찾았다면 index의 왼쪽(index-1)와 오른쪽(index+1)은 연산을 수행해야 할 피연산자인 것이다. 이 원리를 이용하여 3번에 걸쳐 모든 연산자를 사용하면 수식에는 최종 상금이 남게된다.

마지막으로 각 조합마다 최고 상금을 구하는 코드다.

let number = Int64(expressionArray[0]) ?? -2 // nil 병합연산자
        operationResult = (operationResult < abs(number)) ? abs(number) : operationResult // 최대 우승상금 결정

절대값이 가장 큰 경우 최대 상금이므로 삼항연산자를 사용하였다. 문제를 해결한 후 다른 코드를 보았는데 삼항 연산자 대신 아래와 같이 max(_:_:) 함수를 사용하면 더 간결한 코드 작성이 가능하다.

let number = Int64(expressionArray[0]) ?? -2 // nil 병합연산자
operationResult = max(operationResult, abs(number))

max(_:_:)함수를 사용한 코드의 연산횟수는 O(1), 삼항연산자를 사용한 코드의 연산횟수도 O(1)이므로 성능적인 측면에서 차이가 없다. 그러므로 최댓값을 비교하는 코드 작성 시 더 간결한 max(_:_:)함수를 사용하는 게 좋아 보인다.

몰랐던 사실 or 기억하면 도움이 될 만한 사실

max를 이용한 간편한 최댓값 비교?

  • 코드 설명에서 설명함

코드 후기

코드를 작성하면서 처음에 접근한 방법은 스택이나 큐를 이용한 방법이었다. 이전까지 괄호를 이용한 문제들을 스택이나 큐를 사용하였고, 후위 표기식처럼 수식과 관련된 문제 해결에 스택이나 큐를 많이 사용하였기 때문이다. 그러나 이 접근법을 사용하면서 코드를 작성하였는 데, 시간이 오래 소요되고 코드의 복잡성이 증가하였다. (스택이나 큐를 이용하여 간편한 코드가 있을 가능성이 높으나 본인은 해결하지 못함) 그래서 기존의 스택이나 큐를 사용하여야 한다는 고정관념을 버리고 문자열 처리를 진행하니 쉽게 해결할 수 있었다. 앞으로 코드를 작성할 때 무조건 어떤 방법을 사용해야 한다는 것이 아닌 유연한 방법으로 접근하도록 노력해야겠다.

profile
LEEHAKJIN-VV
이전 포스트

예상 대진표

다음 포스트

예산

0개의 댓글