Codility_EquiLeader

8-2. EquiLeader

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

비어 있지 않은 N개의 정수로 구성된 배열 A가 주어집니다.

이 배열의 리더는 A의 요소의 절반 이상에서 발생하는 값입니다.

이퀴 리더는 0 ≤ S < N − 1인 인덱스 S로, 두 시퀀스 A[0], A[1], …, A[S]와 A[S + 1], A[S + 2], …, A[N − 1]이 동일한 값의 리더를 가지는 경우입니다.

예를 들어, 다음과 같은 배열 A가 주어졌을 때:

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

다음과 같은 두 개의 이퀴 리더를 찾을 수 있습니다:

0, 시퀀스: (4)와 (3, 4, 4, 4, 2)가 동일한 리더 값 4를 가집니다. 2, 시퀀스: (4, 3, 4)와 (4, 4, 2)가 동일한 리더 값 4를 가집니다. 목표는 이퀴 리더의 수를 세는 것입니다.

다음과 같은 함수를 작성하세요:

class Solution { 
    public int solution(int[] A); 
}

비어 있지 않은 N개의 정수로 구성된 배열 A가 주어졌을 때, 이퀴 리더의 수를 반환하는 함수를 작성하세요.

예를 들어, 다음과 같은 배열이 주어졌을 때:

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

함수는 위에서 설명한 대로 2를 반환해야 합니다.

다음 가정을 위한 효율적인 알고리즘을 작성하세요:

N은 [1…100,000] 범위 내의 정수입니다.
배열 A의 각 요소는 [−1,000,000,000…1,000,000,000] 범위 내의 정수입니다.

문제풀이

import java.util.*;

class Solution {
    public int solution(int[] A) {
        int N = A.length;
        Map<Integer, Integer> countMap = new HashMap<>();
        
        int leader = A[0];
        int leaderCount = 0;

        for(int num : A){
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
            if(countMap.get(num) > leaderCount){
                leader = num;
                leaderCount = countMap.get(num);
            }
        }

        if (leaderCount <= N / 2) { 
            return 0; 
        }

        int equiLeaders = 0;
        int leftLeaderCount = 0;
        int rightLeaderCount = leaderCount;

        for (int i = 0; i < N; i++) {
            if (A[i] == leader) {
                leftLeaderCount++;
                rightLeaderCount--;
            }

            if (leftLeaderCount > (i + 1) / 2 && rightLeaderCount > (N - i - 1) / 2) {
                equiLeaders++;
            }
        }

        return equiLeaders; 
    }
}

우선 배열 A 만큼 반복문을 돌려 리더를 구합니다.
여기서 "countMap.getOrDefault(num, 0)" -> 해당 값이 없으면 0으로
if문으로 해당 배열의 값이 leaderCount보다 크면 leader와 leaderCount를 해당 값으로 세팅

반복문이 끝나고 leaderCount <= N / 2 일 경우는 리더가 없기에 0을 리턴

A만큼 반복문을 다시 돌려 A[i]가 리더값인 경우를 체크해 이퀴 리더를 카운팅합니다.

제출결과

문제풀어보기 -> https://app.codility.com/programmers/lessons/8-leader/equi_leader/