Codility Lesson 06 - MaxProductOfThree( JAVA )

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

MaxProductOfThree coding task - Learn to Code - Codility

 

문제

- N개의 정수로 이루어진 A배열( 비어있지 않은 배열 )이 주어진다.

- (P, Q, R) = A[P] * A[Q] * A[R]( 0<= P < Q < R  < N)

- (P, Q, R)의 최대값을 구하라.

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

• (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

return 60;

 

제한조건

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

N은 3 ~ 100,000 사이의 정수이다.

A의 각 원소들은 -1,000 ~ 1,000 사이의 정수이다.

 

풀이

- A배열의 개수가 3개 일경우 예외 처리해준다.

- A배열을 오름차순으로 정렬 해준다.

- 정렬 된 후 최대값이 나올 수 있는 경우를 생각해본다( A[0], A[1], A[2] ... A[N-1], A[N] )

- ( A[0], A[1], A[N] ), ( A[N-2], A[N-1], A[N] )이 2가지만이 최대값이 나올 수 있는 경우

- triplet 메소드를 만들어서 풀이한다.

 

예상 시간복잡도 : O(log(N))? 잘 예측되지 않는다..

 

// 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 {
    int triplet(int a, int b, int c){
        return a * b * c;
    }
    
    public int solution(int[] A) {
        // write your code in Java SE 8
        if( A.length == 3 ){
            return triplet(A[0], A[1], A[2]);
        }

        Arrays.sort(A);
        int N = A.length-1;
        int max = Integer.MIN_VALUE;
        if( max < triplet(A[N],A[N-1],A[N-2])){
            max = triplet(A[N],A[N-1],A[N-2]);
        }

        if( max < triplet(A[N],A[1],A[0])){
            max = triplet(A[N],A[1],A[0]);
        }

        return max;
    }
}