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)

 

📝 이 문제는... 

생각없이 풀면 삼중으로 for문을 돌려야 하는데, 좀 더 생각하면 for문을 1도 안쓰고 풀 수 있는 문제이다.

케이스를 직접 작성해보며 문제의 답을 유형화 시키면 잘 풀 수 있다.

 

 

첫번째 풀이: 삼중 for문

 

const largestProductOfThree = function (arr) {
  const multi = []
  for (let i=0; i< arr.length; i++) {
    const remove01 = arr.slice()
    remove01.splice(i,1)
    for(let j=0; j<remove01.length; j++){
      const remove02 = remove01.slice()
      remove02.splice(j,1)
      for(let k=0; k<remove02.length; k++){
        multi.push(arr[i]*remove01[j]*remove02[k])
      }
    }
  }
  return Math.max(...multi)
};

가장 처음 내가 풀었던 풀이 방식이다.

3개의 숫자를 곱해서 가장 큰 것을 구해야 하기 때문에,

일단 구할 수 있는 모든 숫자를 다 해보고, 그 중 가장 큰 것을 찾기로 했다.

다른 풀이 방식을 보니 아주 무식한 방법이 아닐 수 없다.

 

 

 

두번째 풀이: sort + 케이스 스터디

 

const largestProductOfThree = function (arr) {
	arr.sort((a,b)=>a-b)
  const endIdx = arr.length - 1
  
  //음수가 두개이상일 경우 대비
  candi1 = arr[0] * arr[1] * arr[endIdx]
  //가장 큰수 세개 곱하기
  candi2 = arr[endIdx - 2] * arr[endIdx - 1] * arr[endIdx]
  return Math.max(candi1,candi2)
}

 

 

위의 풀이 방법은 아래의 케이스 스터디를 통해 가장 큰 곱이 나올 경우를 유형화 시켜야 한다.

 

[-10,-3,-5,0,1,2,4] //-10 * -3 * 4 = 120 
[-2,-1,0,5,6,7] //5 * 6 * 7 = 210
[-100,-99,-10,-2,-1] //-10 * -2 * -1 = -20
[0,1,2,10,99,100] //10 * 99 * 100


따라서 오름차순으로 정렬된 배열에서
3가지 수를 곱해서 가장 큰 수가 나올 경우의 수는 아래의 두가지 이다.

1️⃣. 첫번째 요소 * 두번째 요소 * 마지막 요소
2️⃣. 마지막 요소 * 마지막에서 두번째 요소 * 마지막에서 세번째 요소