[JavaScript/알고리즘] TapeEquilibrium (feat. 경계값 테스트)

Lesson 3 (Time Complexity) - TapeEquilibrium(Easy)

Test results - Codility

점수: 84/100

 

배열을 두 부분으로 나눠서 각 부분의 합계를 구한 뒤 차이를 구하고, 그 차이의 최솟값을 구하는 문제입니다. 예를 들어서 [3, 1, 2, 4, 3] 이라는 배열이 있다면 3+1+2 / 4+3 으로 나눴을 때의 차이가 1로 가장 작기 때문에 답은 1입니다.

 

초기 코드

function solution(A) {
    let everySum = 0;
    let res = Infinity;
    let sum = 0;

    A.forEach(num => everySum += num);

    for (let i = 0; i < A.length; i++) {
        sum += A[i];
        const difference = Math.abs(sum - (everySum - sum));

        if (res > difference) {
            res = difference;
        }
    }

    return res;
}

 

배열의 모든 수를 더하고 반복문을 돌면서 누적값을 순서대로 빼보는 방법을 사용해보았습니다. 그리고 거기서 최솟값을 비교합니다.

 

function solution(A) {
    console.log(test(new Array(100000).fill(-1000)));
    return 0;
}

function test(A) {
    // 코드 내용
    
    return res;
}

이번에는 이런 식으로 경계값/반복값 테스트를 해보기도 했습니다.

하지만 좀더 철저한 경계값 테스트를 했다면 이 코드의 허점을 발견할 수 있었을텐데... 라는 아쉬움이 드는군요.

 

값을 [1000, -1000] 으로 넣었다면 답은 2000이어야 하지만 위의 코드에서는 0이라는 값이 나왔기 때문이지요.

 

즉, 처음 코드에서 반복문의 범위를 i < A.length가 아닌 i < A.length - 1로 설정해야 했었습니다.

애초에 문제를 잘 읽었다면... 무조건 "두 부분"으로 나눠져야 하므로 두 번째 조각이 없는 경우를 제외시켰을 텐데...

이렇게 또 깨달음을 얻습니다.