[Codility] Lesson 3: Time Complexity - TapeEquilibrium (javascript)

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

Task description

원본 사이트 : https://app.codility.com/programmers/lessons/3-time_complexity/tape_equilibrium/

TapeEquilibrium coding task - Learn to Code - Codility

 

- N 개의 정수로 구성된 비어 있지 않은 배열 A
- A[N] : 테이프의 숫자
- P : 테이프를 두 개로 나눌 위치 (0 < P < N)
- 두 부분의 차이(절대값) = |(A[0]+...+A[P-1]) - A[P]+...+A[N-1])|
- A와 N이 주어질 경우, 최소 차이값 return
- 가장 효율적인 알고리즘 작성
- N은 [2...100,000] 범위의 정수
- A의 각 요소는 [-1,000...1,000] 범위의 정수

 

Solution

CASE 1: 배열의 전체 합 이용 - 84%

// 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 totalSum = A.reduce((a, b) => a + b);    
    let leftSum = 0;
    let rightSum = totalSum;
    let minDiff = Number.MAX_SAFE_INTEGER;
    let diff;

    for(let i in A){
        leftSum += A[i];
        rightSum -= A[i];
        diff = Math.abs(leftSum - rightSum);
        if(diff < minDiff){
            minDiff = diff;
        }
    }

    return minDiff;
}

- totalSum : reduce() 함수를 이용해 배열 A의 전체 합 계산
- leftSum : P로 나눈 테이프의 왼쪽 부분의 합 → A[0]+...+A[P-1]
- rightSum : P로 나눈 테이프의 오른쪽 부분의 합 → A[P]+...+A[N-1]
- minDiff : Javascript 상의 가장 안전한 최대 정수 값
- diff : leftSum과 rightSum의 차이 절대값 → |(A[0]+...+A[P-1]) - A[P]+...+A[N-1])|
- 배열 크기만큼 for문을 돌며 해당 배열의 값을 더하고 빼는 방식으로 leftSum, rightSum을 구하고, 두 값의 차이 절대값을 계산해 minDiff를 return

 

CASE 1: Result

 

CASE 1: Analysis

The following issues have been detected: wrong answers.
For example, for the input [-1000, 1000] the solution returned a wrong answer (got 0 expected 2000).
다음과 같은 문제가 감지되었습니다. 오답.
예를 들어, 입력 [-1000, 1000]에 대해 솔루션이 틀린 답을 반환했습니다 (결과: 0, 예상: 2000).


The following issues have been detected: wrong answers.
For example, for the input [-10, -20, -30, -40, 100] the solution returned a wrong answer (got 0 expected 20).
다음과 같은 문제가 감지되었습니다. 오답.
예를 들어, 입력 [-10, -20, -30, -40, 100]에 대해 솔루션이 틀린 답을 반환했습니다 (결과: 0, 예상: 20).

=> 배열의 전체 합이 0이 되는 경우, 두 부분의 차이 절대값이 제대로 계산되지 않음.

 

CASE 2: 배열의 전체 합 이용 (초기 값 및 for문 변경) - 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 N = A.length;
    const totalSum = A.reduce((a, b) => a + b);
    let leftSum = A[0];
    let rightSum = totalSum - A[0];
    let minDiff = Number.MAX_SAFE_INTEGER;
    let diff;

    for(let P=1; P<N; P++){
        diff = Math.abs(leftSum - rightSum);
        if(diff < minDiff){
            minDiff = diff;
        }
        leftSum += A[P];
        rightSum -= A[P];
    }

    return minDiff;
}

- CASE 1에서의 오류 수정 버전
- leftSum은 A[0]의 값, rightSum은 totalSum-A[0]으로 초기화 → totalSum이 0이 나오는 경우의 오류를 해결하기위해
- 0<P​​<N 범위만큼 for문을 돌며 diff 값 계산 및 비교

- for문 안에서 diff 값을 먼저 계산/비교한 다음, 이후 P 값에 대해 leftSum과 rightSum을 계산

 

CASE 2: Result

 

CASE 2: Analysis

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

결론

최대값이나 최소값 변수 선언 시, Number.MAX_SAFE_INTEGER/Number.Number.MIN_SAFE_INTEGER 상수 활용

 

정확성을 위해서라면 for문을 돌며 모든 P 값에 대해 leftSum과 rightSum을 구해 비교하는 것이 맞겠지만, 퍼포먼스 측면에서는 너무 많은 메모리가 낭비
-> 기준점(P)을 놓고 해당 배열의 값(A[P])을 더하고 빼가며 leftSum과 rightSum을 구하고 비교

[-1000, 1000]과 같이 배열의 전체 합이 0이 되는 경우에 대해 고려 필요
-> leftSum과 rightSum의 초기값을 각각 0과 totalSum으로 하게 되면 모든 값이 다 0으로 설정됨
-> 절대값 계산 결과가 0이 나올 수 밖에 없음

값을 비교하는 순간과 순서에 대해 고려 필요