4. 원소 개수 세기 (Counting Elements) Codility Lesson 한국어 정리본 (JavaScript ver.)

원소 개수 세기란?

배열을 활용하여 숫자 시퀀스를 저장하는 방법에는 여러 가지가 있다. 일반적으로 연속된 숫자 a₀, a₁, ..., aₙ₋₁를 배열의 인덱스에 맞춰 저장한다.

예를 들어:

let A = [4, 2, 4, 5];
// A[0] = 4, A[1] = 2, A[2] = 4, A[3] = 5

그러나 원소를 직접 저장하는 대신, 각 숫자의 등장 횟수를 세는 배열 을 만들 수도 있다.

이 경우, 배열 count[] 는 해당 값이 등장한 횟수를 저장한다.

count[2] = 1; // 숫자 2는 한 번 등장
count[4] = 2; // 숫자 4는 두 번 등장
count[5] = 1; // 숫자 5는 한 번 등장

이 방법을 사용하면 특정 숫자가 등장한 횟수를 O(1) 시간에 확인할 수 있다.

---

1. O(n + m) 시간 복잡도의 원소 개수 세기

다음 함수는 배열 A에 등장하는 각 숫자의 개수를 세는 함수이다.

JavaScript 코드:

function counting(A, m) {
    let n = A.length;
    let count = new Array(m + 1).fill(0);
    for (let k = 0; k < n; k++) {
        count[A[k]] += 1;
    }
    return count;
}

이 함수는 O(n + m) 시간 복잡도를 가진다. m 값이 너무 크면 메모리 사용량이 증가할 수 있다.

---

2. 배열 교환을 통한 합 일치 여부 확인

배열 A와 B가 주어졌을 때, 하나의 원소를 교환하여 두 배열의 합을 동일하게 만들 수 있는지 확인하는 문제이다.

O(n²) (비효율적인 방법)

function slowSolution(A, B, m) {
    let n = A.length;
    let sumA = A.reduce((a, b) => a + b, 0);
    let sumB = B.reduce((a, b) => a + b, 0);
    
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            let change = B[j] - A[i];
            sumA += change;
            sumB -= change;
            
            if (sumA === sumB) return true;
            
            sumA -= change;
            sumB += change;
        }
    }
    return false;
}

이 방법은 모든 가능한 쌍을 교환해보므로 O(n²) 시간이 걸린다.

---

O(n + m) (효율적인 방법)

좀 더 효율적인 방법은 원소 개수를 세는 배열을 활용하는 것이다.

function fastSolution(A, B, m) {
    let n = A.length;
    let sumA = A.reduce((a, b) => a + b, 0);
    let sumB = B.reduce((a, b) => a + b, 0);
    let d = sumB - sumA;
    
    if (d % 2 !== 0) return false;
    d /= 2;
    
    let count = counting(A, m);
    
    for (let i = 0; i < n; i++) {
        if (B[i] - d >= 0 && B[i] - d <= m && count[B[i] - d] > 0) {
            return true;
        }
    }
    return false;
}

이 방법은 O(n + m) 시간 복잡도를 가지며, 더 큰 입력 값에도 효과적으로 실행될 수 있다.