Lesson 8. Leader - Dominator #1

1. 문제

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

 

주어진 배열에서, 가장 많이 등장하는 값(대표값)을 찾는 문제.

단, 등장 횟수가 배열 크기의 절반을 초과해야 한다. 

 

return value: 대표값의 index (index는 어떤 것이든 상관없다)

대표값이 없으면, -1

 

예시) 

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

 

가장 많이 등장하는 값: 3

등장 횟수: 5회 (배열크기 8)

return value: 0, 2, 4, 6, 7 중 아무거나 

 

 

2. 매개변수 조건

배열 크기: 0 ~ 100,000

배열 요소 값의 범위: -2,147,483,648 ~ 2,1,47,483,647

 

 

3. 문제풀이 전략

1. map을 이용해서 <값, 등장횟수>로 정리한다. (배열 전체탐색)
2. map에서 등장 횟수가 가장 큰 값을 찾는다. (map 전체탐색)
3. 등장 횟수가 배열 크기의 절반을 초과하는지 확인한다.

 

4. 코드 (C++)

대표값이 없는 경우(빈 배열, 등장 횟수 조건 미충족)를 주의해야 한다.

#include <map>
#include <algorithm>

int solution(vector<int> &A) {

    if(A.empty()) return -1; //빈 배열

    map<int, int> candidate = {};

    //등장 횟수 세기, map<값, 등장횟수>으로 저장한다
    for(size_t i = 0; i < A.size(); i++)
    {
        auto it = candidate.find(A[i]);
        if(it == candidate.end())
        {
            candidate.insert(pair<int, int>(A[i], 1));
        }
        else
        {
            it->second += 1;
        }
    }

    // 가장 많이 등장한 값 찾기
    int dominator = 0;
    int cnt = 0;
    for(auto& v : candidate)
    {
        if(v.second > cnt)
        {
            dominator = v.first;
            cnt = v.second;
        }
    }

    //대표값이 등장 횟수 조건을 충족하는지 확인
    if(cnt <= A.size() / 2) return -1;

    auto it = find(A.begin(), A.end(), dominator);
    int idx = distance(A.begin(), it);
    
    return idx;
}

 

 

5. 결과