[Codility] Lesson8 - Leader : EquiLeader (c++)

Problem

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].
  
  app.codility.com/programmers/lessons/8-leader/equi_leader/

EquiLeader coding task - Learn to Code - Codility

How to solve

- 정보

N의 길이를 가진 배열 A

leader: A 데이터 중 절반 이상 나오는 값(빈도수가)

Equi leader: A를 2 구간으로 나누었을 때, 두 구간의 지배자가 모두 A의 배열의 지배자인 idx 갯수 return 

 

- 구해야 하는것?

배열 A를 2구간으로 나누었을 때, 

나누어진 두 구간에서의 지배자가 전체배열 A의 지배자와 같은 경우를 equi leader라고 하고, 

equi leader인 경우의 수 return

 

- 예시

A =[4, 3, 4, 4, 4, 2] 으로 주어진 배열이라면,

4              3 4 4 4 2      (Equi leader) 왼쪽 구간 leader 4, 오른쪽 구간 leader 4

4 3            4 4 4 2        -------------  왼쪽 구간 leader 없음, 오른쪽 구간 leader 4

4 3 4          4 4 2        (Equi leader) 왼쪽 구간 leader 4, 오른쪽 구가 leader 4

4 3 4 4       4 2            -------------  왼쪽 구간 leader 4, 오른쪽 구간 leader 없음

4 3 4 4 4     2              -------------  왼쪽 구간 leader 4, 오른쪽 구간 leader 2

 

이기 때문에 Equi Leader의 경우의 수 는 2이다. 

 

 

- 풀이

1) leader와 해당 leader가 나온 횟수를 구한다.

    (mirae-kim.tistory.com/122 참고)

2) 두 구간에서 의 leader count를 구해야 하기 때문에, 

  left_cnt: 왼쪽 구간에서의 leader count

  right_cnt: 오른쪽 구간에서의 leader count

  를 구한다. 

  -> 구하는 방법은 

      idx=0 일때, left_cnt =0, right_cnt=max_val로 놓고,

      idx 를 증가시키며, leader가 나올 때마다 left_cnt++, right_cnt-- 를 한다.

3) 왼쪽구간과 오른쪽구간에서 leader인지 check 한다. 

 

**주의 사항**

A의 원소가 1개일 때는, 2 구간으로 나눌 수 없기 때문에 0 return 

A의 원소 중 leader의 수(max_val) 이 A의 원소의 수/2 보다 작으면, 

두 구간으로 나누어도 leader가 있을 수 없기 때문에 0 return.

 

Solution(c++)

// you can use includes, for example:
#include <bits/stdc++.h>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    int len = A.size();
    int max_val = 0;
    int leader;
    int res = 0;
    map<int, int> leader_cnt; 

    // 1 element
    if(len == 1){
        return 0;
    }

    // several elements
    for(int i=0; i<len; i++){
        if(leader_cnt.find(A[i]) == leader_cnt.end()){
            leader_cnt[A[i]] = 1;    
        }else{
            leader_cnt[A[i]]++;
            if(max_val < leader_cnt[A[i]]){
                max_val = leader_cnt[A[i]];
                leader = A[i];
            }
        }
    }
    
    if(max_val < len/2 ){
        return 0;
    }

    int left_cnt = 0;
    int right_cnt = leader_cnt[leader];

    for(int i=0; i<len; i++){
        // A의 원소가 leader일때
        if(A[i] == leader){
            left_cnt++;
            right_cnt--;
        }
        // 양 구간에서 모두 leader인 경우 res++
        if(right_cnt > (len-(i+1))/2 && left_cnt > (i+1)/2){
            res++;
        }
    }
    return res;
}

Test Result

app.codility.com/demo/results/trainingD3EWSG-M5S/

Test results - Codility