Lesson 8. Leader - EquiLeader #1

1. 문제

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

 

EquiLeader를 찾는 문제.

EquiLeader란? 배열을 두 개(좌, 우)로 나눴을 때, 양쪽의 Leader 값이 같은 것이다.

단, Leader는 배열의 절반 이상을 차지해야 한다. 

 

예시) return 2

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

 

EquiLeader는 2개가 있다.

• case 1: (4) , (3, 4, 4, 4, 2) / Left Leader: 4 , Right Leader: 4
• case 2: (4, 3, 4) , (4, 4, 2) / Left Leader: 4 , Right Leader: 4 

 

2. 매개변수 조건

• 배열A 크기: 1 ~ 100,000
• 배열A 요소 값 범위: -1,000,000,000 ~ 1,000,000,000

 

3. 코드 (C++)

Leader를 구하는 것은 Dominator #1 #2 #3-1 #3-2 에서 충분히 다뤘다.

아래 코드는 Dominator #3-2 코드를 이용해서 Leader를 구했다. 

#include <limits>

int find_leader(vector<int> &A, int start, int end)
{
    int leader = 0;
    int cnt = 0;
    for(int i = start; i < end; i++)
    {
        if(cnt == 0)
        {
            leader = A[i];
            cnt = 1;
        }
        else
        {
            if(A[i] != leader) cnt--;
            else cnt++;
        }
    }

    cnt = 0;
    for(int i = start; i < end; i++)
    {
        if(A[i] == leader) cnt++;
    }

    if( cnt <= ((end - start) / 2) )
    {
        return numeric_limits<int>::min();
    } 

    return leader;
}

int solution(vector<int> &A) {

    int range = 1;
    int cnt = 0;
    while(range < A.size())
    {
        int left_leader = find_leader(A, 0, range); //left leader 구하기
        if(left_leader == numeric_limits<int>::min())
        {
            range++;
            continue;
        } 

        int right_leader = find_leader(A, range, A.size()); //right leader 구하기
        if(right_leader == numeric_limits<int>::min())
        {
            range++;
            continue;
        } 

        //두 leader가 같으면 equi leader
        if(left_leader == right_leader) cnt++;
        range++;
    }

    return cnt;
}

 

 

4. 결과