Lesson 6 - 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:

class Solution { public int solution(int[] A); }

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].

---

첫번째 풀이

요구사항에 충실.. O(N)³ 이므로 당연하게 실패한다.

class Solution {
    public int solution(int[] A) {
        int maximumTriplet = -Integer.MAX_VALUE;

        for(int i=0; i<A.length-2; i++) {
            int P = A[i];

            for(int j=i+1; j<A.length-1; j++) {
                int Q = A[j];

                for(int k=j+1; k<A.length; k++) {
                    int R = A[k];

                    int triplet = P * Q * R;
                    
                    if(maximumTriplet < triplet) {
                        maximumTriplet = triplet;
                    }
                }
            }
        }

        return maximumTriplet;
    }
}

---

두번째 풀이

답의 도출만 신경쓴다.

정렬 후에 가장 뒤쪽에 제일 큰 숫자만 뽑아보려 노력한다.

0 혹은 음수가 존재하는 상황이 생기므로 그런 경우의 케이스에서 실패하였다.

가장 큰 수를 얻으려면 모두 양의 정수이던지, 음수가 2개 양수가 1개인 경우의 양의 정수를 뽑을 수 있는데 어떻게 그런 케이스를 고려할 수 있을까?

import java.util.Arrays;

class Solution {
    public int solution(int[] A) {
        Arrays.sort(A);
        return A[A.length-1] * A[A.length-2] * A[A.length-3];
    }
}

---

베스트 답안

여기에 적혀있는 답이 나의 고민을 해결해주었다.

정렬 후에
1. 첫3개
2. 마지막 3개
3. 처음2개 마지막1개
4. 처음1개 마지막 2개

의 총 4개 케이스 중 max 값을 뽑아서 답을 얻어냈다.

이렇게 하면 음수2개 정수 1개 숫자로 가장 큰 값을 얻어낼 수 있다.

   public int solution(int[] A) {
    List aList = new ArrayList();
    for(int i=0; i<A.length; i++) {
      aList.add(A[i]);
    }
    Collections.sort(aList);
   
    int product1, product2, product3, product4 = 0;

    product1 = aList.get(0) * aList.get(1) * aList.get(2); //first 3 elements
    product2 = aList.get(aList.size()-3) * aList.get(aList.size()-2) * aList.get(aList.size()-1); //last 3 elements
    product3 = aList.get(0) * aList.get(1) * aList.get(aList.size()-1); //first 2 and last element
    product4 = aList.get(0) * aList.get(aList.size()-2) * aList.get(aList.size()-1); //first and last 2 elements

    int max1 = Math.max(product1, product2);
    int max2 = Math.max(product3, product4);
   
    return Math.max(max1, max2);
  }

더 짧게 답을 적으신 분도 있다.

class Solution {
    public int solution(int[] A) {

        // main idea: 
        // max_1 = positive * positive * positive
        // max_2 = negative * negative * positive
        // max = Math.max(max_1, max_1)
        // just need to sort the integer array
        
        // sort the array
        Arrays.sort(A);

        // max_1 = 1st biggest * 2nd biggest * 3rd biggest 
        int max_1 = A[A.length-1] * A[A.length-2] * A[A.length-3];
        
        // max_2 = 1st smallest * 2nd smallest * 1st biggest
        int max_2 = A[0] * A[1] * A[A.length-1];

        // take the maximum        
        int max = Math.max(max_1, max_2);
        
        return max;
    }
}