[Codility] Lesson 6: Sorting - MaxProductOfThree (javascript) 문제 풀이

깃허브 : https://github.com/miiingo/codility

Task description

원본 사이트 : app.codility.com/programmers/lessons/6-sorting/max_product_of_three/

MaxProductOfThree coding task - Learn to Code - Codility

 

- N 개의 정수로 구성된 비어있지 않은 배열 A가 제공
- 삼중항 (P, Q, R)의 곱은 A[P] * A[Q] * A[R] (0 ≤ P < Q < R < N)과 동일
- 삼중항의 최대 곱의 값을 return
- 가장 효율적인 알고리즘 작성
- N은 [3..100,000] 범위의 정수
- 배열 A의 각 요소는 [-1,000..1,000] 범위의 정수

 

Solution

CASE 1: Array.sort() 이용 - 44%

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    const sortA = A;
    const N = A.length;
    let triplet;
    
    sortA.sort(function(a, b) {
        return a - b;
    });
    triplet = sortA[N-3] * sortA[N-2] * sortA[N-1];
    
    return triplet;
}

- sortA : 배열 A를 복사한 새로운 배열
- N : 배열 A의 길이
- triplet : 최대 삼중항의 값
- sortA 배열을 오름차순으로 정렬한 뒤, 배열의 가장 끝에 있는 3 개 요소의 곱을 return

 

CASE 1: Result

 

CASE 1: Analysis

The following issues have been detected: wrong answers.
For example, for the input [-5, 5, -5, 4] the solution returned a wrong answer (got -100 expected 125).
다음과 같은 문제가 감지되었습니다. 오답.
예를 들어, 입력 [-5, 5, -5, 4]의 경우 솔루션에서 잘못된 답변을 반환했습니다 (예상: 125, 결과: -100).

-> 음수가 포함되어 있는 경우에 대해 고려 필요

 

CASE 2: 음수의 곱과 양수의 곱을 비교 추가 - 66%

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    const sortA = A;
    const N = A.length;
    let left, right, triplet;
    
    sortA.sort(function(a, b) {
        return a - b;
    });
    
    left = sortA[0] * sortA[1];
    right = sortA[N-2] * sortA[N-1];
    if(left > right) {
        triplet = left * sortA[N-1];
    }else {
        triplet = right * sortA[N-3];
    }
    
    return triplet;
}

- left : sortA의 왼쪽 끝에 있는 두 수의 곱
- right : sortA의 오른쪽 끝에 있는 두 수의 곱
- 음수의 곱이 양수가 되는 경우가 있으므로 left와 right 값을 비교
- left 값이 더 클 경우, left에 가장 큰 정수인 sortA[N-1]을 곱함
- right 값이 더 크거나 같을 경우, right에 포함되지 않은 숫자들 중의 가장 큰 정수인 sortA[N-3]을 곱함

 

CASE 2: Result

 

CASE 2: Analysis

The following issues have been detected: wrong answers.
For example, for the input [-5, -6, -4, -7, -10] the solution returned a wrong answer (got -280 expected -120).
다음과 같은 문제가 감지되었습니다. 오답.
예를 들어 입력 [-5, -6, -4, -7, -10]의 경우 솔루션에서 잘못된 답변을 반환했습니다 (예상: -120, 결과: -280).

=> 음수만 있을 경우에는 가장 작은 음의 정수 3 개를 곱하는 게 가장 큰 결과가 나옴

 

CASE 3: 모든 수가 음수인 경우 예외 처리 추가 - 77%

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    const sortA = A;
    const N = A.length;
    let left, right, triplet;
    
    sortA.sort(function(a, b) {
        return a - b;
    });
    
    if(sortA[N-1] <= 0) {
        triplet = sortA[N-3] * sortA[N-2] * sortA[N-1];
    }
    else {
        left = sortA[0] * sortA[1];
        right = sortA[N-2] * sortA[N-1];
        if(left > right) {
            triplet = left * sortA[N-1];
        }else {
            triplet = right * sortA[N-3];
        }
    }
    
    return triplet;
}

- CASE 2에서 sortA[N-1]<=0인 경우 예외 처리 추가
- sortA[N-1]<=0이면, 어떤 값을 선택하던 음수 또는 0의 값이 나오게 되므로 가장 작은 세 개의 음수를 곱하는 것이 가장 큰 삼중항 결과가 나옴
- 음수가 1개/2개인 경우에는 left, right 값을 비교해서 결과 출력

 

CASE 3: Result

 

CASE 3: Analysis

The following issues have been detected: wrong answers.
For example, for the input [4, 7, 3, 2, 1, -3, -5] the solution returned a wrong answer (got 84 expected 105).
다음과 같은 문제가 감지되었습니다. 오답.
예를 들어 입력 [4, 7, 3, 2, 1, -3, -5]의 경우 솔루션에서 잘못된 답변을 반환했습니다 (예상: 105, 결과: 84).

=> 양쪽 끝의 두 개 값의 곱만 비교하는 것이 아닌, 세 값의 곱을 비교해야함.

 

CASE 4: 모든 예외 처리 추가 완료 - 100%

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    const sortA = A;
    const N = A.length;
    let left, right, triplet;
    
    sortA.sort(function(a, b) {
        return a - b;
    });
    
    if(sortA[N-1] <= 0) {
        triplet = sortA[N-3] * sortA[N-2] * sortA[N-1];
    }
    else {
        left = sortA[0] * sortA[1] * sortA[N-1];
        right = sortA[N-3] * sortA[N-2] * sortA[N-1];
        if(left > right) {
            triplet = left;
        }else {
            triplet = right;
        }
    }
    
    return triplet;
}

- 양쪽 끝의 두 개 값의 곱만 비교하는 것이 아닌, 세 값의 곱을 비교
- sortA[N-1]<=0이면, triplet의 값은 가장 작은 세 개 음수의 곱이 됨
- left와 right 중 더 큰 값이 triplet 값이 됨

 

CASE 4: Result

 

CASE 4: Analysis

The solution obtained perfect score.
이 솔루션은 완벽한 점수를 얻었습니다.

 

결론

배열 A의 값을 순서대로 정렬한 뒤, 가장 큰 3 개 값의 곱을 구하면 끝이라고 생각했는데 결과 값이 음수일 경우에 대한 고려가 생략되어 잘못된 결과가 나옴

음수가 있는 경우에 대한 고려 필요!

배열 A의 모든 숫자가 음수일 경우, 가장 작은 세 개의 음수를 곱하는 것이 가장 큰 결과가 됨
나머지 경우, 음수의 곱도 양수가 되므로 left와 right 곱의 값을 비교해서 결과 출력

쉽게 생각했지만 계속해서 실수하며 헤멘 문제