2020 카카오 인턴쉽 수식 최대화 Swift

문제 설명

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 이하가 되도록 입력이 주어집니다.
• 같은 연산자끼리는 앞에 있는 것의 우선순위가 더 높습니다.

---

입출력 예

expression	result
"50*6-3*2"	300
"100-200*300-500+20"	60420

Foma의 풀이

 

1. 연산자의 갯수를 알아내어 우선순위조합을 만들어낼수 있느냐

 

2 .식에 포함된 숫자와 연산자를 각각 분리해낼 수 있느냐

 

3. 우선순위조합대로 각 식의 연산자의 위치를 알아내어 위치에 맞는 숫자들을 연산하고 식을 재정립할수 있는가

 

4. 우선순위조합대로 연산한 식의 절대값 중 가장 최대값을 반환할수 있는가

 

제가 생각한 핵심은 이렇게 4가지입니다.

 

자세한 풀이는 아래에 설명하겠습니다.

 

 

expression에서 각 연산자의 위치를 담아줄 배열들을 만들어준다. => var minus = [Int]() var multiple = [Int]() var plus = [Int]()

 

바뀔 식을 담을 배열을 만들어준다. => var numbers = [String]()

 

while문에 필요한 숫자를 저장할 변수를 만들어준다. => var j = Int()

 

(다른 함수가 있기 때문에 반드시 위의 변수들은 solution함수 밖에다가 만들어준다.)

 

그리고 연산자의 우선순위 조합들을 담을 2차원 배열을 만들어준다. => var order = [[String]]()

 

우선순위조합대로 연산했을 때의 값들을 저장할 배열을 만들어준다. = >  var sums = [Int64]()

 

연산자 배열을 넣을 집합을 만들어준다.(집합으로 만드는 이유는 중복을 없애 주어진 연산자의 갯수를 알아내야되기 때문이다.) => var oper = Set<String>()

 

exprssion을 필터로 연산자일때로 걸러주고 맵으로 배열로 만들어줘 포함되어 있는 연산자들을 담아준다.

=> var operArray = expression.filter({$0 == "+" || $0 == "-" || $0 == "*"}).map{String($0)} ex) "50+3-10*6+9"이라면 opreArray는 ["+",-","*","+"]

 

formUnion을 사용해 집합에 위의 연산자들을 담은 배열을 넣어줘 중복을 없애준다.

=> oper.formUnion(operArray)

 

우선순위조합을 만들기위해선 집합의 인덱스를 사용해야하므로 집합을 배열로 바꿔준다.(집합의 인덱스를 사용해도 되지만 배열이 편해서 배열로 바꿔줌) => let operSetArray = Array(oper)

 

 연산자 개수가 1개에서 최대 3개이므로 각각의 경우의 수는 1!,2!,3!이므로 얼마되지 않아서 직접 order에 조합을 만들어서 넣어줬습니다.

   => if oper.count == 1 {

        order.append([operSetArray[0]]) => ex) ["+"] or  ["-"] or ["*"]

    } else if oper.count == 2 {

만약 +,-일경우

        order = [[operSetArray[0],operSetArray[1]],[operSetArray[1],operSetArray[0]]] => ex) ["+","-"],["-",+"]

    }else{

        order = [[operSetArray[0],operSetArray[1],operSetArray[2]],[operSetArray[0],operSetArray[2],operSetArray[1]],[operSetArray[1],operSetArray[0],operSetArray[2]],[operSetArray[1],operSetArray[2],operSetArray[0]],[operSetArray[2],operSetArray[1],operSetArray[0]],[operSetArray[2],operSetArray[0],operSetArray[1]]]

=> ex) ["+","-","*"],["+","*","-"].....

    }

 

그 다음으로 for문을 사용하여 order에 있는 조합들을 차례로 돌려줍니다.

=> for c in order {...}

 

expression을 연산자를 기준으로 분리해서 숫자들만 따로 numbers에 담아줍니다.

=> numbers = expression.components(separatedBy: CharacterSet(charactersIn: "*-+")) ex)"50+3-10" 이라면 number = ["50"],["3"],["10"]

 

expression에서 연산자들만 모은 배열값을 넣어줍니다.. (뒤에 operArray가 삭제되기 때문에 반드시 다시 값을 넣어줘야합니다..)

 operArray = expression.filter({$0 == "+" || $0 == "-" || $0 == "*"}).map{String($0)}

 

while문을 만들어서 numbers의 숫자 배열과 expression의 연산자 배열을 차례로 섞어 실제 식에서 숫자와 연산자를 분리한 배열을 만들어줍니다. (for문을 사용하여 배열을 만들시엔 만약 "50+3"이라면 숫자 50을 구분하기 힘들어서 이렇게 섞어서 만들어주었습니다.)

ex) 50 + 3 - 6 + 8 * 7이라면 numbers는 ["50", "+" ."3", "-", "6", "+", "8","*",'7"] 

var x = 1

        while x < numbers.count{

            numbers.insert(operArray.first!, at: x)

 

그리곤 minus,plus,multiple에 각각 해당 인덱스를 넣어줍니다. ex) numbers가 ["50", "+" ."3", "-", "6", "+", "8","*",'7"] 이라면 plus = [1,5] minus = [3] mutiple = [7]

            if operArray.first! == "-"{

                minus.append(x)

            }else if operArray.first! == "+"{

                plus.append(x)

            }else {

                multiple.append(x)

            }

            operArray.removeFirst()

            x += 2

        }

 

while문을 사용하여 detectMMP라는 연산자를 구분하는 함수를 실행시켜줍니다.

시작할 때 만들어놓은 j를 0으로 만들어줍니다 => j = 0

        while j < c.count {

            detectMMP(c.map({$0})[j]) c는 order안의 값 map핑해주고 차례로 꺼내줍니다. ex)"+","-","*"

        }

 

그리곤 detectMMP를 살펴보면 인자값으로 order의 연산자를 차례로 받게됩니다. 

func detectMMP(_ oper:String){ 

plus,minus,multiple배열의 값을 저장할 변수를 만들어줌 => var mmpCopy = [Int]()

 

그리고 차례로 "+","-","*"일 경우에 numbers의 각 배열의 해당인덱스 자리의 - 1값과 해당인덱스의 +1 값을 연산자에 맞게 연산해줍니다.

numbers가 ["50", "+" ."3", "-", "6", "+", "8","*",'7"] 이고 "+"일 경우엔 plus는 가장 첫번째 인덱스가 1이므로 numbers의 -1자리는 0이고 +1 자리는 2이므로 각각 50 + 3이되고 numbers[0]의 값은 53으로 변하고 전체는 ["53", "+" ."3", "-", "6", "+", "8","*",'7"]이 됩니다.

   => if oper == "+" {

        mmpCopy = plus

        numbers[plus.first! - 1] =  "\(Int(numbers[plus.first! - 1])! +  Int(numbers[plus.first! + 1])!)"

 

그리고 plus의 첫번째 값을 삭제해주고

   => plus.removeFirst()

 

만약 plus가 한 개가 아닐시엔 j값을 더해주지않아 다시 while문에서 "+"가 오도록합니다.

        if plus.isEmpty {

            j += 1

        }

 

그리고 numbers에서 해당 인덱스의 연산자와 뒤에 더해준 값을 삭제시켜줍니다.

ex)  ["53", "+" ."3", "-", "6", "+", "8","*",'7"]  ->  ["53",  "-", "6", "+", "8","*",'7"] 

   numbers.remove(at: mmpCopy.first!)

   numbers.remove(at: mmpCopy.first!)

 

그리고 numbers에서 연산자와 더해준 값이 총 2개가 없어지므로 그 뒤에 식들의 인덱스를 -2를 해줍니다.

ex) numbers = ["53", "+" ."3", "-", "6", "+", "8","*",'7"] 라면 뒤에 "+'와 "3"이 없어지므로 ["53", "-", "6", "+", "8","*",'7"]

minus = [3]에서  -> miuns [1]으로 mutiple = [7]에서 multiple [5]로 바뀌게 됩니다.

    plus = plus.filter{$0 <= mmpCopy.first!}.map{$0} + plus.filter{$0 > mmpCopy.first!}.map{$0-2}

 

그 다음 다시 solution으로 돌아가서 numbers의 하나남은 값을 절대값으로 변형에 sums에 넣어줍니다.(절대값으로 변형하기 위해선 Int64형으로 바꿔줘야함) => sums.append(abs(Int64(numbers.first!)!))

 

마지막으로 이렇게 추가된 sums에서 가장 큰 값을 반환해줍니다. => return sums.max()!

 

 

전체코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112

import Foundation   //- 연산자의 index를 담을 배열 var minus = [Int]() //* 연산자의 index를 담을 배열 var multiple = [Int]() //+ 연산자의 index를 담을 배열 var plus = [Int]() //식을 담을 배열 var numbers = [String]() //while문에 필요한 숫자 var j = Int()   func solution(_ expression:String) -> Int64 {          //연산자 우선순위 조합들을 담을 2차원배열     var order = [[String]]()     //각 우선순위 연산했을때 넣어줄 값     var sums = [Int64]()     //연산자 배열을 넣을 집합     var oper = Set<String>()     //exprssion에 포함되어 있는 연산자 배열     var operArray = expression.filter({$0 == "+" || $0 == "-" || $0 == "*"}).map{String($0)}     //Set oper에 mmp를 넣어줘서 중복을 없앤다      oper.formUnion(operArray)     //우선순위조합을 만들기 위해 Set를 배열로 만들어줌     let operSetArray = Array(oper)          //연산자 갯수만큼 우선순위 조합     if oper.count == 1 {         order.append([operSetArray[0]])     } else if oper.count == 2 {         order = [[operSetArray[0],operSetArray[1]],[operSetArray[1],operSetArray[0]]]     }else{         order = [[operSetArray[0],operSetArray[1],operSetArray[2]],[operSetArray[0],operSetArray[2],operSetArray[1]],[operSetArray[1],operSetArray[0],operSetArray[2]],[operSetArray[1],operSetArray[2],operSetArray[0]],[operSetArray[2],operSetArray[1],operSetArray[0]],[operSetArray[2],operSetArray[0],operSetArray[1]]]     }          //우선순위조합을 순서대로 꺼낼 for문     for c in order {         //연산자를 기준으로 숫자들을 나눠서 담아준다.         numbers = expression.components(separatedBy: CharacterSet(charactersIn: "*-+"))         //연산자들만 있는 배열을 다시 복구         operArray = expression.filter({$0 == "+" || $0 == "-" || $0 == "*"}).map{String($0)}         var x = 1         //숫자들과 연산자들을 각 위치에 맞게 배열로 만들어준다.         while x < numbers.count{             numbers.insert(operArray.first!, at: x)             if operArray.first! == "-"{                 minus.append(x)             }else if operArray.first! == "+"{                 plus.append(x)             }else {                 multiple.append(x)             }             operArray.removeFirst()             x += 2         }           j = 0                  //j가 연산자의 갯수보다 적다면을 조건으로 while문을 돌림         while j < c.count {             //detectMMP에 +,-,* 인지 넣어줌             detectMMP(c.map({$0})[j])         }         //마지막으로 남은 numbers의 절대값을 값을 저장하는 sums에 넣어줌         sums.append(abs(Int64(numbers.first!)!))     }     //sums에 있는 제일 큰 수를 return해준다.     return sums.max()! }   func detectMMP(_ oper:String){          var mmpCopy = [Int]()          //만약 우선순위조합중 차례로 연산자를 알아내고 plus배열에서 가장 첫번째 인덱스를 찾고 numbers에서 그 기호 앞 뒤의 숫자들을 각 연산기호에 맞게 해준다.     if oper == "+" {         mmpCopy = plus         numbers[plus.first! - 1] =  "\(Int(numbers[plus.first! - 1])! +  Int(numbers[plus.first! + 1])!)"         //연산이 끝나면 해당 연산자를 담는 배열의 첫번째 인덱스를 삭제해준다.         plus.removeFirst()         //만약 연산기호가 여러개일땐 j를 그대로 유지해 다시 그 연산자로 되돌아오게한다.         if plus.isEmpty {             j += 1         }     }else if oper == "-" {         mmpCopy = minus         numbers[minus.first! - 1] =  "\(Int(numbers[minus.first! - 1])! -  Int(numbers[minus.first! + 1])!)"         minus.removeFirst()         if minus.isEmpty {             j += 1         }       }else if oper == "*"{         mmpCopy = multiple         numbers[multiple.first! - 1] =  "\(Int(numbers[multiple.first! - 1])! *  Int(numbers[multiple.first! + 1])!)"         multiple.removeFirst()         if multiple.isEmpty {             j += 1         }    }    //식에서 삭제해준 연산자의 위치를 삭제해준다. 한번 더 해주는 이유는 두 숫자를 연산하면 연산자 뒤의 숫자가 자동으로 없어지기 때문이다.     numbers.remove(at: mmpCopy.first!)     numbers.remove(at: mmpCopy.first!)     //그 다음 각 연산자의 인덱스 중 전에 삭제된 인덱스보다 큰 값이라면 -2를 해준다. 왜냐하면 연산자와 두 숫자가 연산되어 하나의 숫자가 되므로 2개의 값이 삭제된다.     plus = plus.filter{$0 <= mmpCopy.first!}.map{$0} + plus.filter{$0 > mmpCopy.first!}.map{$0-2}     multiple = multiple.filter{$0 <= mmpCopy.first!}.map{$0} + multiple.filter{$0 > mmpCopy.first!}.map{$0-2}     minus = minus.filter{$0 <= mmpCopy.first!}.map{$0} + minus.filter{$0 > mmpCopy.first!}.map{$0-2}        }   Colored by Color Scripter

cs

새롭게 알게 된것들

Set에 배열 전체를 넣기위해선 Set.formUnion(Array)

 

String에서 여러개의 separator를 사용하려면 String.components(separatedBy: CharacterSet(charactersIn: "원하는것들"))

 

절대값을 알아내기 위해선 abs(Int64(Number))