[Algorithm] largestProductOfThree

입력 받은 배열에서 값 3개를 가지고 나올 수 있는 경우의 수 중에 가장 큰 값을 고르시오.

let output = largestProductOfThree([2, 1, 3, 7]);
console.log(output); // --> 42 (= 2 * 3 * 7)

output = largestProductOfThree([-1, 2, -5, 7]);
console.log(output); // --> 35 (= -1 * -5 * 7)

처음 문제를 봤을 때,
가장 큰 값을 찾기 위해서 for문을 이용해서 찾을려니까
for문을 3번이나 돌려야되는 크나큰 문제점이 발견 되었다.
아마 초보자의 이러한 헛점을 노린 문제인 것 같다.

키 포인트는 배열에서의 최대값 최솟값은 .sort()내장함수를 이용해서
구할 수 있다는 점.

 const sorted = arr.sort((a, b) => a - b);

하지만 sort는 mutates한 성질 때문에

값을 한 변수에 저장을 해줘야한다.

이미 정렬이 된 상태면 거의 끝났다.

마지막 뒤에 3개의 값이 가장 큰 값이 되는 것은 당연하다.

왜냐하면 오름 차순으로 정리를 했기 때문이다.

[5,9,1,3] => [1,3,5,9] => 가장 큰 값은 3,5,9

즉, 배열의 가장 뒤에서 부터 3개의 값을 끄집어 내면 그것은 최댓값.

const len = sorted.length;
const result = sorted[len - 1] * sorted[len - 2] * sorted[len - 3];

return result;

이 된다.

근데 한가지 빼먹은 사실 만약

오름 차순으로 정리한 값이 이러한 배열이라면?

[-13, -11, 2, 3, 5, 7]

뒤에서 부터 3개의 값을 끄집어낸 357보다

-13 * -11 * 7 이 값이 크게된다.

고로, 음수 * 음수는 양수가 나온다는 점을 이용해야 한다.

그럼 -는 가장 작을 수록 가장 앞에 나온 값이니까

어차피 음수 x 음수를 진행 할려면 가장 작은 두 수를 곱하는 것이 양수로 변하면서 가장 큰 값을 만드는 방법이며 이미 양수로 만들었으니 마지막 값으로는 정렬의 가장 오른 쪽 값이 가장 큰 값으로 생각해주면 된다.

이러한식을 고려하면

arr[0] * arr[1] * arr[arr.length - 1] 이 된다.

최종 정리를 하면

const largestProductOfThree = function (arr) {
  // TODO: 여기에 코드를 작성합니다.
  //const sorted = arr.slice().sort((a, b) => a - b);
  const sorted = arr.sort((a, b) => a - b);
  //const len = arr.length;
  const len = sorted.length;
  const candi1 = sorted[len - 1] * sorted[len - 2] * sorted[len - 3];
  const candi2 = sorted[len - 1] * sorted[0] * sorted[1];
  return Math.max(candi1, candi2);

};

음수가 올때 양수가 올때를 변수 candi1,2로 나눠서

둘 중에 가장 큰 값을 출력(Math.max())하면 굳이 조건문으로 나누지 않아도 값을

찾을 수 있다.