8. 리더 (Leader) Codility Lesson 한국어 정리본 (JavaScript ver.)

리더(Leader)란?

주어진 수열 A = [a₀, a₁, ..., aₙ₋₁] 에서 리더(Leader) 는 수열의 원소 중 절반을 초과하여 등장하는 원소 를 의미한다.

예를 들어, 다음과 같은 수열이 있을 때:

A = [6, 8, 4, 6, 8, 6, 6];

위 수열에서 6은 4번 등장하여 n/2 = 3.5 보다 많이 등장하므로 리더가 된다. 리더는 최대 하나만 존재 한다.

---

1. O(n²) 시간 복잡도의 단순한 방법

각 원소의 등장 횟수를 세어 리더를 찾는 방법이다.

JavaScript 코드:

function slowLeader(A) {
    let n = A.length;
    let leader = -1;
    
    for (let k = 0; k < n; k++) {
        let candidate = A[k];
        let count = 0;
        for (let i = 0; i < n; i++) {
            if (A[i] === candidate) {
                count++;
            }
        }
        if (count > Math.floor(n / 2)) {
            leader = candidate;
        }
    }
    return leader;
}

시간 복잡도: O(n²) (모든 원소를 반복적으로 비교)

---

2. O(n log n) 시간 복잡도의 정렬 기반 방법

배열을 정렬하면 같은 값들이 인접하게 모이므로, 중앙값(A[n/2])이 리더일 가능성이 높다.

JavaScript 코드:

function fastLeader(A) {
    let n = A.length;
    A.sort((a, b) => a - b);
    let candidate = A[Math.floor(n / 2)];
    let count = A.filter(x => x === candidate).length;
    
    return count > Math.floor(n / 2) ? candidate : -1;
}

시간 복잡도: O(n log n) (정렬 후 단순 반복)

---

3. O(n) 시간 복잡도의 스택 기반 방법

아이디어:

• 서로 다른 두 원소를 제거해도 리더는 변하지 않는다.
• 스택을 활용해 서로 다른 원소를 제거하면서 남은 원소를 리더 후보로 선택한다.
• 마지막으로 리더 후보의 등장 횟수를 세어 실제 리더인지 확인한다.

JavaScript 코드:

function goldenLeader(A) {
    let n = A.length;
    let size = 0;
    let value;
    
    for (let k = 0; k < n; k++) {
        if (size === 0) {
            size++;
            value = A[k];
        } else {
            size += (A[k] === value) ? 1 : -1;
        }
    }
    
    let candidate = -1;
    if (size > 0) {
        candidate = value;
    }
    
    let count = A.filter(x => x === candidate).length;
    return count > Math.floor(n / 2) ? candidate : -1;
}

시간 복잡도: O(n) (각 원소를 한 번씩만 탐색)