[Codility] Lesson 6 : MaxProductOfThree - JAVA

문제

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

Copyright 2009–2022 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

 

문제 해설

solution(int[] A)에 입력되는 배열 A의 길이(N)는 3 ~ 100,000이고
배열 A에 저장되는 정수의 범위는 -1,000 ~ 1,000이다.

배열 A에서 값을 3개 꺼내서 곱해줬을 때 가장 큰 값이 무엇인지 찾아 반환하면 된다.

예를 들어 
        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
이므로 가장 큰 값은 60이며 이 값을 반환해주면 된다.

 

풀이 - 1

import java.util.Arrays;
class Solution {
    public int solution(int[] A) {
        int N = A.length;
        Arrays.sort(A);
        int max = A[N-1] * A[N-2] * A[N-3];
        if(max < (A[N-1] * A[0] * A[1])) max = A[N-1] * A[0] * A[1];
        return max;
    }
}

 

'풀이 - 1'에 대한 회고

 

문제는 쉽다.

먼저 오름차순이던 내림차순이던 정렬을 먼저 하고,

오름차순인 경우 가장 마지막 값 3개를 곱해주면 된다.

반대로 내림차순이면 가장 앞에 있는 값 3개를 곱해주면 된다.

 

그런데 이렇게 생각하다가 테스트 케이스를 놓쳤다.

만약 가장 작은 값 2개가 음수면?

그럼 양수 중 가장 큰 값이랑 가장 작은 음수 2개를 곱해주면 훨씬 더 커지지 않을까?

그래서 조건문을 통해 한 번 더 비교를 해줬다.

 

 

결과는 정확도, 퍼포먼스 모두 100%

 

 

다른 사람은 어떻게 풀었는지 확인해봐야겠다.

 

다른 사람의 풀이

import java.util.Arrays;
class Solution {
    public int solution(int[] A) {
        int N = A.length;
        Arrays.sort(A);
        int maxA = A[N-1] * A[N-2] * A[N-3];
        int maxB = A[N-1] * A[0] * A[1];
        return Math.max(maxA, maxB);
    }
}

 

'다른 사람의 풀이'를 통한 회고

 

다른 사람의 풀이도 크게 차이는 없다.

그래도 내가 작성한 코드보다 가독성이 좋아서 가져왔다.

 

일단 다양한 테스트 케이스가 있을 것으로 생각하고 코드를 작성하는 버릇을 길러야겠다.

그리고 읽기 좋게 깔끔하게 작성하도록 하자!