[Codility] Equi Leader

링크 : https://app.codility.com/programmers/lessons/8-leader/equi_leader/

 

풀고 나서 이게 쉬움이라고??? 했던 문제 🤔🤔🤔

우선 Equi 리더를 만족 시키려면 원본 배열에 무조건 leader 숫자가 있어야 하고, 해당 숫자가 Equi 리더 배열에서도 leader 숫자일 것이다. 원본 배열의 leader 숫자가 아니였던 숫자는 equi leader 배열의 leader 숫자가 될 수 없을 것이다. 

 

해당 가정으로 먼저 원본 배열에서 leader 숫자와 leader 숫자의 index 들을 찾아낸다. 

그 다음 equi leader 을 찾아내기 위해 원본 배열을 순회한다.

인덱스 기준으로 배열을 두 개로 나눈 뒤에, 아까 찾았던 leader 숫자의 index 를 이용하여 나눠진 각 배열마다 leader 숫자의 갯수를 구한다. 

나눠진 각 배열의 총 요소 갯수와 leader 숫자의 갯수를 이용해 leader 숫자 조건에 부합하는지 확인한다.

나눠진 두 배열 모두 leader 숫자 조건에 부합하면 equi leader 카운트를 올려준다.

 

bool isLeader(int count, int arrSize)
{
    return count > arrSize / 2;
}

int solution(vector<int>& arr) 
{
    unordered_map<int, vector<int>> numIndexes;

    int maxCount = 0;
    int leaderNum = 0;

    for (int index = 0; index < arr.size(); ++index)
    {
        int num = arr[index];

        vector<int> arrTemp;
        auto iter = numIndexes.emplace(num, arrTemp);
        auto& vec = iter.first->second;

        vec.push_back(index);
       
        if (vec.size() > maxCount)
        {
            maxCount = vec.size();
            leaderNum = num;
        }
    }

    if(!isLeader(maxCount, arr.size()))
    {
        return 0;
    }

    const vector<int>& leaderIndexes = numIndexes.find(leaderNum)->second;
    int arrSize = arr.size();
    int firstSectionLeaderCount = 0;
    int secondSectionLeaderCount = leaderIndexes.size();
    int equiCount = 0;
    int leaderIndex = 0;

    for (int index = 0; index < arrSize - 1; ++index)
    {
        if (leaderIndex <= leaderIndexes.size() - 1)
        {
            if (leaderIndexes[leaderIndex] == index)
            {
                ++firstSectionLeaderCount;
                --secondSectionLeaderCount;
                ++leaderIndex;
            }
        }
        
        int firstSectionSize = index + 1;
        int secondSectionSize = arrSize - firstSectionSize;

        if (isLeader(firstSectionLeaderCount, firstSectionSize) &&
            isLeader(secondSectionLeaderCount, secondSectionSize))
        {
            ++equiCount;
        }
    }

    return equiCount;
}