#33 TIL - splice 시간 복잡도 문제 해결하기

JavaScript 성능 최적화: 배열 정렬 및 요소 제거

해당 포스는 이전 포스트에서 말했던 splice 메서드의 시간복잡도 문제를 해결하기 위해
JavaScript에서 배열을 정렬하고 요소를 제거하는 작업을 최적화하는 방법에 대해 알아보려 한다.

특히 splice 메서드를 사용하였을때 발생한 문제와, 이를 최적화한 코드 작성에 대해 중점적으로 다루겠다.

이전포스트보러가기

문제 상황

입력 데이터의 크기가 매우 클 때, 특히 score 배열의 길이가 최대 1,000,000인 경우, 정렬 및 요소 제거 작업에서 성능 문제가 발생할 수 있다.

특히, Array.prototype.sort() 메서드는 O(n log n)의 시간 복잡도를 가지며, 대규모 배열에서 성능 저하의 주요 원인이 된다.

이전 코드와 문제점

function Restriction(k, m, score) {
    if (k < 3 || k > 9) return false;
    if (m < 3 || m > 10) return false;
    if (score.length < 7 || score.length > 1000000) return false;
    if (score.some(s => s < 1 || s > k)) return false;
    return true;
}

function solution(k, m, score) {
    if (!Restriction(k, m, score)) {
        throw new Error("Restriction Violation!");
    }

    // 배열을 내림차순으로 정렬
    score.sort((a, b) => b - a);

    let totalValue = 0;

    while (score.length >= m) {
        // m 개씩 뽑아서 상자를 만든다.
        let box = score.splice(0, m);

        // 상자의 최저 점수를 구한다.
        let minScore = Math.min(...box);

        // 상자의 가치를 계산한다.
        totalValue += minScore * m;
    }

    return totalValue;
}

문제점 분석

1. splice 사용: splice는 배열의 중간에서 요소를 제거할 때 비효율적이다. 특히 큰 배열에서는 성능이 저하되는 문제가 발생한다.
2. 최소값 계산: Math.min(...box)를 사용하여 최소값을 계산하는 방식은 추가적인 연산을 필요로 한다.
3. 반복문 내 조건 확인: while 루프는 조건을 반복적으로 확인하므로 추가적인 연산이 발생한다.

최적화

최적화 방법

1. 정렬 최적화: 정렬을 한 번만 수행하여 반복적인 정렬을 피한다.
2. splice 제거: splice를 사용하지 않고 인덱스를 이용하여 고정된 크기의 상자를 만든다.
3. 루프 최적화: for 루프를 사용하여 불필요한 반복을 줄인다.

function Restriction(k, m, score) {
    if (k < 3 || k > 9) return false;
    if (m < 3 || m > 10) return false;
    if (score.length < 7 || score.length > 1000000) return false;
    if (score.some(s => s < 1 || s > k)) return false;
    return true;
}

function solution(k, m, score) {
    if (!Restriction(k, m, score)) {
        throw new Error("Restriction Violation!");
    }

    // 배열을 내림차순으로 정렬
    score.sort((a, b) => b - a);

    let totalValue = 0;

    // m 개씩 상자를 만들어 계산한다.
    for (let i = 0; i <= score.length - m; i += m) {
        // 상자의 최저 점수를 구한다.
        let minScore = score[i + m - 1];

        // 상자의 가치를 계산한다.
        totalValue += minScore * m;
    }

    return totalValue;
}

// 예제 테스트
let k = 3;
let m = 4;
let score1 = [1, 2, 3, 1, 2, 3, 1];
console.log(solution(k, m, score1)); // 8

let k2 = 4;
let m2 = 3;
let score2 = [4, 1, 2, 2, 4, 4, 4, 4, 1, 2, 4, 2];
console.log(solution(k2, m2, score2)); // 33

최적화된 부분 설명

1. splice 사용 제거:

   • 이전 코드에서 splice를 사용하여 요소를 제거하는 방식 대신, for 루프와 인덱스를 사용하여 필요한 요소를 참조한다. 이를통해 메모리 사용을 최적화하고 성능을 향상시킨다.

2. 최소값 계산 최적화:

   • 정렬된 배열에서 인덱스를 사용하여 상자의 마지막 요소를 최소값으로 간주한다.
     이 방법을 통해 Math.min 함수 호출을 피하면서도 정확한 최소값을 얻을 수 있게 한다.

3. 루프 최적화:

   • for 루프를 사용하여 일정한 간격으로 인덱스를 증가시키며 상자를 만든다.
     이는 배열 길이를 참조하지 않고 반복 조건을 명확히 하여 불필요한 조건 확인을 제거한다.

성능 비교

• 이전 코드: 시간 복잡도가 O(n log n) (정렬) + O((n/m) * m) (splice 및 최소값 계산)로 인해 대규모 배열에서 성능이 저하될 수 있다.
• 최적화된 코드: 시간 복잡도가 O(n log n) (정렬) + O(n/m) (상자 생성 및 최소값 계산)로 개선되어 대규모 배열에서도 더 나은 성능을 제공한다.

최적화 과정을 통해 불필요한 배열 변형을 피하고, 최소값 계산을 단순화하며, 반복문을 최적화하여 시간 초과 문제를 해결할 수 있었다.