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

Problem

An array A consisting of N integers is given. The dominator of array A is the value that occurs in more than half of the elements of A.

For example, consider array A such that

A[0] = 3 A[1] = 4 A[2] = 3 A[3] = 2 A[4] = 3 A[5] = -1 A[6] = 3 A[7] = 3

The dominator of A is 3 because it occurs in 5 out of 8 elements of A (namely in those with indices 0, 2, 4, 6 and 7) and 5 is more than a half of 8.

Write a function

int solution(vector<int> &A);

that, given an array A consisting of N integers, returns index of any element of array A in which the dominator of A occurs. The function should return −1 if array A does not have a dominator.

For example, given array A such that

A[0] = 3 A[1] = 4 A[2] = 3 A[3] = 2 A[4] = 3 A[5] = -1 A[6] = 3 A[7] = 3

the function may return 0, 2, 4, 6 or 7, as explained above.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [0..100,000];
• each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].
  
  
  app.codility.com/programmers/lessons/8-leader/dominator/

Dominator coding task - Learn to Code - Codility

How to solve

- 정보

N길이의 정수 배열 A

A 배열의 지배자: A 데이터 중 절반 이상 나오는 값(빈도수가)

 

- 구해야 하는것?

배열 A의 지배자 idx return, 지배자가 없으면 -1 return

 

- 예시

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

3이 5번 이상 나오므로 (전체 8번 중 4번 이상) 지배자는 3이다. 

3의 인덱스는 0, 2, 4, 6, 7이고 

이 중 1개를 return 하면 된다. 

 

- 풀이

map으로 풀기!

1) dominator_cnt : 나온 원소의 갯수를 세는 map 생성

2) 배열 A의 원소가 0 or 1인 경우 처리

3) A벡터를 순회하며, dominator_cnt map에 key가 있으면 value값을 +1

   key 가 없으면 map에 key=A원소, value=1 추가

   value 값이 절반을 넘으면 그때의 idx 값 return

 

**주의 사항**

원소의 갯수가 0 or 1일때

배열 A의 원소의 갯수가 1개 인경우 return 0, 0개인 경우 return -1

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();
    map<int, int> dominator_cnt; 
    
    if(len == 0){
        return -1;
    }else if(len == 1){
        return 0;
    }

    for(int i=0; i<len; i++){
        // A[i] not in dominator_cnt
        if(dominator_cnt.find(A[i]) == dominator_cnt.end()){
            dominator_cnt[A[i]] = 1;
            // cout <<"not exist" << A[i] << endl;
            // cout <<"cnt" << dominator_cnt[A[i]] << endl;
        }else{
            dominator_cnt[A[i]]++;
            if(dominator_cnt[A[i]] > len/2){
                return i;
            }
            // cout <<"exist" << A[i] << endl;
            // cout <<"cnt" << dominator_cnt[A[i]] << endl;
        }
    }
    return -1;
}

Test Result

 

app.codility.com/demo/results/trainingV33KUD-32M/

Test results - Codility