알고리즘 5 : largestProductOfThree

문제 :

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

입력 :

• 인자 1 : 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. 삼중반복문

const largestProductOfThree = function (arr) {

  let list = []
  for(let i = 0;i<arr.length-2;i++){
    for(let j=i+1;j<arr.length-1;j++){
      for(let k = j+1;k<arr.length;k++){
        list.push(arr[i]*arr[j]*arr[k])
      }
    }
  }
  return Math.max(...list)

2. 정렬(출제의도)

const largestProductOfThree = function (arr) {

  let list = arr.sort((a,b)=>a-b)
  const v1 = list[list.length-1]*list[list.length-2]*list[list.length-3]
  const v2 = list[list.length-1]*list[0]*list[1]
  return Math.max(v1,v2)
};

 

 

상세코드

 

처음에는 제일 큰값 3개를 뽑아서 계산을 했다. 그렇게 하면 음수가 있을때 통과하지 못했다.

가장 큰 수 3개를 뽑아서 곱하면 [-5,-4,-3,-1,999,10000] 의 경우에서 
200000을 리턴하지 않고, -9990000 를 리턴했다.

 

그래서 노가다로 3중반복문을 했는데 생각보다 쉬웠다.

 

하지만 다른방법이 있을거라 생각하고 검색을 하다가 새로운 방법을 찾았다.

 

오름차순으로 정렬한 후, Case1(가장 큰 수 3개를 곱한 경우) 와 Case2(가장 작은수 2개와 가장 큰수 1개 곱한경우) 를 비교하는 것이다.

그 후 Case1과 Case2를 비교하여 큰 값을 리턴하는 것이다.

 이렇게 하는 이유는 arr = [-50,-20,-30,-5,40]인 경우를 대비하는 것이다.