Codility - MaxProductOfThree

아래 문제는 코딜리티에서 제공하는 Sorting > MaxProductOfThree의 문제입니다🧑🏻‍💻

 

문제 제시

A non-empty array A consisting of N integers is given. The product of triplet (P, Q, R) equates to A[P] * A[Q] * A[R] (0 ≤ P < Q < R < N).

For example, array A such that:

A[0] = -3 A[1] = 1 A[2] = 2 A[3] = -2 A[4] = 5 A[5] = 6

contains the following example triplets:

• (0, 1, 2), product is −3 * 1 * 2 = −6
• (1, 2, 4), product is 1 * 2 * 5 = 10
• (2, 4, 5), product is 2 * 5 * 6 = 60

Your goal is to find the maximal product of any triplet.

Write a function:

public func solution(_ A : inout [Int]) -> Int

that, given a non-empty array A, returns the value of the maximal product of any triplet.

For example, given array A such that:

A[0] = -3 A[1] = 1 A[2] = 2 A[3] = -2 A[4] = 5 A[5] = 6

the function should return 60, as the product of triplet (2, 4, 5) is maximal.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [3..100,000];
• each element of array A is an integer within the range [−1,000..1,000].

 

 

문제 풀이

public func solution(_ A : inout [Int]) -> Int {
   let sortedA = A.sorted()
   let count = sortedA.count

   let sumOfPositiveMaxA = sortedA[count - 1] * sortedA[count - 2] * sortedA[count - 3]
   let sumOfNegativeMaxA = sortedA[0] * sortedA[1]
   let sumOfCombinatedMaxA = sumOfNegativeMaxA * sortedA[count - 1]

   if sumOfNegativeMaxA > 0 {
     return max(sumOfCombinatedMaxA, sumOfPositiveMaxA)
   }

   return sumOfPositiveMaxA
 }

 

사용 개념

- sort

- max 

 

문제 후기

해당 문제는 구현은 쉬웠으나 양수/음수에 대한 고려까지 하여 조금 더 간단한 코드를 생각해내기에 초점이 맞춰졌습니다.

우선 아주 단순히 3개의 요소를 곱했을때 가장 큰 수를 뽑아내면 되는거라 흔히들 반복문을 돌려버려 접근하려 할겁니다.

그랬을때 문제점은 음수가 걸립니다.

즉, 음수의 절대값이 최대 양수값보다 클 수 있고 그 음수는 양수가 되려면 무조건 두개가 곱해져야 하죠.

그래서 반복문으로는 이 조건을 만족시키며 구현하기에는 코드가 더러워질것 같습니다.

그래서 우선 input A를 정렬했습니다.

그 뒤 배열 제일 뒤에 있는 즉, 가장 큰 양수 3개의 곱을 구합니다.

그리고 배열에서 가장 먼저 있는 가장 작은 수 두개의 곱을 구합니다.

그리고 위 가장 작은 수 두개의 곱과 가장 큰 양수의 곱을 구해요.

이러면 결국 어떤 배열이 들어와도 3개의 합이 가장큰것은 3개의 구한 상수에서 판단할 수 있죠.

이 외 다른 변수는 없습니다.

그 다음으로 가장 작은 수의 2개의 곱이 양수일때와 음수일때로 판단할 수 있습니다.

음수라면 음수끼리의 곱이 아니니 어떤 양수를 곱해도 음수가 되니 의미가 없습니다.

그러니 최대 양수 3개의 곱을 리턴해줘요.

만약 위 조건이 양수라면 음수 두개의 곱임을 파악할 수 있죠.

이럴때는 앞서 구한 가장작은 수 2개와 가장 큰 양수의 곱과 순서대로 큰 양수 3개의 곱 중 큰 값의 비교를 위해 max 메서드를 사용해주고 리턴시켜버리면 됩니다.

 

사실 아주 단순한 구현인데 사고를 달리하기가 어려울 수 있는 그런 충분한 문제였다고 생각합니다.

 

[참고 자료]

https://app.codility.com/programmers/lessons/6-sorting/max_product_of_three/

MaxProductOfThree coding task - Learn to Code - Codility