[Codility] Sorting - MaxProductOfThree 풀이

예문

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

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

해석

  • A : N개의 정수로 구성 된 비어있지 않은 배열
  • 삼중 항 (P, Q, R) : A[P] * A[Q] * A[R] (0 ≤ P < Q < R < N).
  • 삼중 항의 최대 값을 리턴해라!

풀이

  • 우선 정렬 시킨다.
  • 모두 양수 일 경우
    • 1 2 3 4 5 6 = A[N-1] * A[N-2] * A[N-3]
  • 모두 음수 일 경우
    • -6 -5 -4 -3 -2 -1 = A[N-1] * A[0] * A[1]
  • 음수, 양수 혼합 일 경우
    • -1 -2 -3 -4 -5 6 = A[N-1] * A[N-2] * A[N-3]
  • A[N-1] 은 항상 곱해진다.
  • A[N-1] 이 음수, 양수 여부에 따라 최소값, 최대값을 구해준다.

제약사항

  • N의 범위는 정수 [3..100,000]
  • 배열A의 각 요소의 범위는 정수 [−1,000..1,000]

코드

import java.util.Arrays;
public int solution(int[] A) {
  Arrays.sort(A);

  int N = A.length;
  int firstProduct = A[0] * A[1];
  int secondProduct = A[N - 3] * A[N - 2];
  int lastProduct = A[N - 1];

  if (lastProduct < 0) return Math.min(firstProduct, secondProduct) * A[N - 1];
  else return Math.max(firstProduct, secondProduct) * A[N - 1];
}

결과