알고리즘: largestProductOfThree

문제

정수를 요소로 갖는 배열을 입력받아 3개의 요소를 곱해 나올 수 있는 최대값을 리턴해야 합니다.

입력

인자1 : arr

number 타입을 요소로 갖는 임의의 배열

출력

number 타입을 리턴해야 합니다

주의사항

입력으로 주어진 배열은 중첩되지 않은 1차원 배열입니다.
배열의 요소는 음수와 0을 포함하는 정수입니다.
배열의 길이는 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)

풀이

1. sort()함수 오름차순으로 나열하기
2. 음수 + 양수인 조합 시
   2.1. 맨앞 2개 + 맨뒤 1개
3. all 음수 or all 양수 조합 시
   3.1. 맨 뒤에서 3개
4. 그중 큰 값을 고르기

const largestProductOfThree = function (arr) {
  // TODO: 여기에 코드를 작성합니다.
  let head = 0;
  let tail = 0;

  arr.sort((a,b) => a-b ) // 오름차순으로 정리

  head = arr[0] * arr[1] * arr[arr.length-1] // 음수 양수 혼합시 
  tail = arr[arr.length-1] * arr[arr.length-2] * arr[arr.length-3] // 모두 음수이거나 모두 양수일 때

  if(head > tail) {
    return head;
  } else {
    return tail;
  }
  // or return Math.max(head, tail);
};

한 줄평

• 오름차순으로 나열할 생각까지는 했다
• 처음에는 음수가 홀수개인 경우와 짝수개인 경우로 나눠서 접근하려고 하니 경우의 수가 너무 많이 생겨졌다
• A: 음수와 양수가 섞여있다고 가정하면,
  - 음수가 짝수개 일 시 절대값이 가장 큰 음수 2개와 절대값이 가장 큰 짝수 1개가 선택된다 (최대값으로 채택 O)
  • 음수가 홀수개 일 시 (최대값으로 채택 X)
• B: 모두 음수 or 모두 양수 일 시 절대값이 가장 큰 마지막 3개를 선택한다
  - 모두 음수일 경우 (최대값으로 채택 X)
  • 모두 양수일 경우 (최대값으로 채택 0)
• A와 B중 최대값인 경우를 내보내면 된다