[LeetCode] 343번: Integer Break [Swift]

문제 링크 

Integer Break - LeetCode

문제

Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.

 

Example 1:

Input: 2 Output: 1 Explanation: 2 = 1 + 1, 1 × 1 = 1.

Example 2:

Input: 10 Output: 36 Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.

Note: You may assume that n is not less than 2 and not larger than 58.

 

문제 풀이

처음 문제를 볼 땐 많은 경우의 수를 비교할 생각에 조금 막막했다. 하지만 마음을 비우고 규칙성을 찾기 위해 예로 주어진 10까지 직접 손으로 계산하다 보니 규칙성을 발견했다!

 

2 = 1 + 1

3 = 1 + 2

4 = 2 + 2

5 = 2 + 3

6 = 3+ 3

7 = 2 + 2 + 3

8 = 2 + 3 + 3

9 = 3 + 3 + 3

10 = 2 + 2 + 3 + 3

 

위와 같은 형태의 규칙을 가지고 있었다. n이 2,3 일때를 제외하면 모든 경우에서 2,3으로 덧셈을 구성할 때가 해당 값들을 곱했을 때 가장 큰 값이 나왔다. 사실.. 다른 방법이 있을 수 있지만 나는 이렇게 풀었다.

위의 규칙은 3의 배수 즉 덧셈을 구성하는 수가 모두 3일 경우 다음수는 3을 하나 없애고 2를 2개 추가하면 그것이 답이 된다. 

또한 2보다는 3이 우선적으로 생각되어야한다. 예를 들어 n = 7 일 때 3 + 3 + 1로 나타낼 수 있지만 이는 2,3으로 구성된 값이 아니기 때문에 3을 한 개 줄인 3 + 2 + 2 가 답이 되는 것이다.

소스 코드

class Solution{
    func integerBreak(_ n: Int) -> Int {
        
        if n == 2 {
            return 1
        } else if n == 3 {
            return 2
        } else {
            let temp: Int = n - 1
            let threeCount: Int = ((temp / 3) - 1) + temp % 3
            let twoCount: Int = (n - 3 * threeCount) / 2
            var result: Int = 1
            for _ in 0..<threeCount {
                result *= 3
            }
            
            for _ in 0..<twoCount{
                result *= 2
            }
            return result
        }
    }
}

사실 제곱을 계산하는 방법에 pow(Double,Double) 방법이 있었고 Xcode에서는 잘 작동되었는데 leetCode에 제출할 때 자꾸 오류가 나서 그냥 위와 같이 for in 구문으로 처리했다.

속도자랑 ^~^