[Codility - Counting Elements] MaxProductOfThree

문제 링크

MaxProductOfThree coding task - Learn to Code - Codility

 

- N 은 3 이상 100,000 이하이다. 따라서, 최악의 경우 모든 triplet의 경우의 수는 99998*99997*99996 이므로 당연히 시간초과가 난다. 따라서 다른 방법을 사용해야 한다.

 

function solution(A) {
    A.sort((a,b)=>a-b)
    let answer = A[A.length-1]*A[A.length-2]*A[A.length-3]
    answer = Math.max(A[0]*A[1]*A[A.length-1], answer)
    return answer
}

 

- sort를 해준 후, 가장 오른쪽의 3개의 세트를 곱한 값이 answer 후보군이 된다.

 

- 다음으로, 음수 2개 * 양수 1개를 곱한 값이 더 큰 양수가 될 수 있다. 따라서, 가장 처음 두 값과 맨 오른쪽 값을 곱한 값과 비교해서 더 큰 수를 반환하면 된다.

 

- 배열의 갯수가 3개일 때, 4개일 때 , 5개 등등일 때, 음수가 2개,3개,4개 등등의 경우의 수를 모두 고려해볼 수 있는데 결과적으로 위의 코드대로 하면 원하는 값이 나오게 된다.