Lesson 8 - 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].

---

최빈 값을 얻어내는 건 어제 풀었으므로 답을 얻었는데 부분합풀이 부분에서 시간을 많이 투자해서 결국 풀지 못했다.

베스트 답안

• 최빈수는 정렬한후에 중앙 값으로 얻을 수 있다.
• 이때 array를 그대로 넘기면 얕은복사이므로 Arrays.copy로 깊은 복사를 한다.
• accumulator 배열에 leader count값을 index 마다 적어 놓는다. (부분 합)
• 배열을 쪼개서 비교하는 대신에, accumulator 배열에서 좌측과 우측의 leaderCnt가 배열의 length/2 (1개는 세야하므로 +1) 이상일 경우 equiCnt를 올린다.

import java.util.Arrays;
class Solution {
    public int solution(int[] A) {
       int equiCnt = 0;
       int N = A.length; 
       if (N < 2) {
           return equiCnt;
       }

       int leader = getLeader(Arrays.copyOf(A, N));

       int[] accumulator = new int[N];

       int accumulatedCount = 0; 
       for(int i=0; i<N; i++) {
           if (A[i] == leader) {
               accumulatedCount++;
           }
           accumulator[i] = accumulatedCount;           
       }

        for( int i=0; i<N-1; i++ ){
            int halfLimitBefore = (i+1) / 2;
            int halfLimitAfter = ( N - (i+1) ) / 2;

            int beforeLeaderCnt = accumulator[i];
            int afterLeaderCnt = accumulator[N-1] - accumulator[i];
            // leader는 과반수 이상어야 함
            if( beforeLeaderCnt > halfLimitBefore && afterLeaderCnt > halfLimitAfter ){
                equiCnt++;
            }
        }

       return equiCnt;
    }


    private int getLeader(int[] arr) {
        Arrays.sort(arr);
        return arr[arr.length/2];
    }
}