(Coldility) EquiLeader - Javascript

문제

 

A non-empty array A consisting of N integers is given.

The leader of this array is the value that occurs in more than half of the elements of A.

An equi leader is an index S such that 0 ≤ S < N − 1 and two sequences A[0], A[1], ..., A[S] and A[S + 1], A[S + 2], ..., A[N − 1] have leaders of the same value.

For example, given array A such that:

A[0] = 4 A[1] = 3 A[2] = 4 A[3] = 4 A[4] = 4 A[5] = 2

we can find two equi leaders:

• 0, because sequences: (4) and (3, 4, 4, 4, 2) have the same leader, whose value is 4.
• 2, because sequences: (4, 3, 4) and (4, 4, 2) have the same leader, whose value is 4.

The goal is to count the number of equi leaders.

Write a function:

function solution(A);

that, given a non-empty array A consisting of N integers, returns the number of equi leaders.

For example, given:

A[0] = 4 A[1] = 3 A[2] = 4 A[3] = 4 A[4] = 4 A[5] = 2

the function should return 2, as explained above.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [1..100,000];
• each element of array A is an integer within the range [−1,000,000,000..1,000,000,000]

 

코드

 

function solution(A) {
    const n = A.length;

    const left = {};
    const right = {};

    for (let i = 0; i < n; i++) {
        const now = A[i];
        right[now] = right[now] === undefined ? 1 : right[now] + 1;
    }

    let leftLength = 0;
    let leftLeader = 0;
    let leftLeaderCount = 0;
    let rightLength = A.length;
    let answer = 0;

    // 오른쪽 요소 하나를 왼쪽으로 옮긴다.
    for (let i = 0; i < n; i++) {
        const now = A[i];
        right[now] -= 1;
        rightLength -= 1;

        left[now] = left[now] === undefined ? 1 : left[now] + 1;
        leftLength += 1;
        
        // 왼쪽으로 옮긴 요소의 개수가 기존 왼쪽 리더의 개수보다 많을 경우
        if (left[now] > leftLeaderCount) {
            leftLeader = now;
            leftLeaderCount = left[now];
        }
        
        // 현재 왼쪽의 리더가 오른쪽에서 리더이고, 그 리더의 개수가 왼쪽에서도 계속 리더일 경우
        // answer 증가.
        if (right[leftLeader] > parseInt(rightLength / 2) && leftLeaderCount > parseInt(leftLength / 2)) {
            answer += 1;
        }
    }

    return answer;
}

 

 

풀이

 

맨 처음 접근법은 먼저 배열을 파라미터로 받아 리더를 구하는 함수를 만들고, 기존 배열을 왼쪽과 오른쪽으로 나눈 뒤 만든 함수를 호출하여 구했었는데 O(N제곱)의 시간 복잡도로 인해 통과하지 못하였고, 위 코드와 같이 왼쪽 배열과 오른쪽 배열의 각 요소마다 개수 정보를 가지고 있는 left, right 객체를 만들고 right의 요소들을 left로 하나씩 옮기면서 구하면 O(N)으로 통과할 수 있다!