[Codility - Java] 8. Leader - 2. EquiLeader

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:

class Solution { public int solution(int[] 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].

---

비어있지 않은 N개의 정수로 구성된 배열 A
leader는 배열 A에 반보다 크게 있는 값입니다.

equi leader S는 배열 A를 특정 인덱스를 기준으로 두부분으로 나눴을 때 양쪽 모두에 동일한 leader를 만족하는 인덱스를 의미합니다.

배열 내에서 존재할 수 있는 equi leader의 개수를 반환하면 됩니다.

---

배열 A의 leader를 먼저 구합니다.
leader가 없을 경우 equi leader를 구하는 것이 의미가 없어지기 때문에 0을 바로 리턴합니다.

leader를 구하는 부분은 [Codility - Java] 8. Leader - 1. Dominator를 참고해주세요.

leader를 구한 후, 다시 배열 A를 순회하면서, leader와 동일한 값일 경우 temp에 카운트를 누적하여 왼쪽 배열과 오른쪽 배열이 각각 equi leader를 만족하는 배열인지를 확인하는 구문을 작성합니다.

왼쪽 배열 길이(현재 인덱스에 1을 더한 것)에 2를 나눈것보다 왼쪽 count가 클 경우 왼쪽은 equi leader를 만족하는 배열이고
오른쪽 배열 길이(배열 A길이에 ()현재 인덱스+1)을 뺀 것)에 2를 나눈 것보다 오른쪽 count(총 count - temp)가 클경우 오른 쪽도 equi leader를 만족하는 배열이므로, 두 조건을 만족할 경우 result를 1 증가시킵니다.

static int equiLeader(int[] A) {
    int leader = 0, size = 0;
    for (int a : A) {
        if (size == 0) {
            size++;
            leader = a;
        } else {
            if (leader == a) {
                size++;
            } else {
                size--;
            }
        }
    }
    if(size < 1) return 0;
    int count = 0;
    for (int i = 0; i < A.length; i++) {
        if(A[i] == leader) {
            count++;
        }
    }
    if(count <= A.length/2)
        return 0;
    int result = 0, temp = 0;
    for (int i = 0; i < A.length; i++) {
        if(A[i] == leader) {
            temp++;
        }
        if((i + 1) / 2 < temp && (A.length - (i + 1))/2 < count - temp) {
            result++;
        }
    }

    return result;
}

$O(N)$

---

codility 결과