Codility[Lesson 6] - Sorting(MaxProdictOfThree)

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

 

 

1차시도 생각없이

// you can also use imports, for example:
import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
        
        Arrays.sort(A);
        
        int max = Integer.MIN_VALUE;

        for(int i=0; i<A.length; i++){
            for(int j=i+1; j<A.length; j++){
                for(int k=j+1; k<A.length; k++){
                    int temp = A[i] * A[j] * A[k];

                    if(max<temp) max = temp;
                }
            }
        }
        return max;

    }
}

당연히 퍼포먼스 점수가 0점 나왔다.....

 

생각해보니 배열안의 3수의 곱이 가장 큰 수는 가장 큰 값들을 곱한것이 가장 클 것...

배열을 정렬 한 후 가장 큰 수들만 곱해서 리턴하면 된다.

// you can also use imports, for example:
 import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8

        Arrays.sort(A);
        int leng = A.length-1;

        int max = A[leng] * A[leng-1] * A[leng-2];

        if(A[0]<0 && A[1] <0 && A[leng]>0){

            int temp = A[0] * A[1] * A[leng];

            if(temp>max) max = temp;

        }

        return max;
    }
}

물론 음수 곱하기 음수는 양수가 되므로 가장 작은수와 가장 작은수의 다음번째가 두개다 음수이고, 가장 큰 수가 양수이면 해당 값도 최대값이 될 가능성이 있으므로 예외처리 해주었더니 100점 나왔다.