[Codility] 8.2 EquiLeader

8.2 EquiLeader

두 개의 구간으로 나누었을 때, 두 구간의 leader가 같은 경우의 수를 구하는 문제이다.
이때 leader의 정의는 전에 다룬 정의와 동일하다

The leader of this array is the value that occurs in more than half of the elements of A.
배열 A의 원소들 중에서 절반보다 많이 존재하는 원소가 리더이다

두 구간의 leader가 같다면, 그 leader는 동시에 전체구간의 leader가 된다는 아이디어에서 시작한다. (각 구간에서 절반보다 많이 존재하므로 당연하다.)

다음과 같이 문제를 풀었다

1. leader를 구한다 (6, 6.1 참고)
   1.1 leader가 없다면 조건을 만족하는 개수는 0이므로 return 0
2. leader의 개수를 누적합으로 구한다
3. 두 개의 구간에서의 leader가 전체 구간에서의 leader와 같다면 개수증가

3개의 단계 모두 $O(n)$이므로 전체 시간복잡도는 $O(3n)= O(n)$이다.

아래코드의 변수설명

st[ ] : leader를 찾기 위한 스택
candidate : A에서 가장 많이 존재하는 원소. 즉, leader의 후보값이다
leader : A의 leader. candidate가 절반보다 많이 존재하면 leader이다
leader_count : A에서 leader의 개수
dp[x] : A[x]까지의 leader의 개수
cur_count : 현재 탐색까지의 leader의 개수
ans : 정답의 개수

index = x일때,앞 구간은 [0...x]이고, 뒷구간은 [x+1, ...N-1]이다
앞구간의 leader의 개수는 dp[x]이고, 구간의 길이는 x+1이다
뒷구간의 leader의 개수는 leader_count - dp[x]이고, 구간의 길이는 N-(x+1)이다

def solution(A):
    # find leader of A
    st = []
    for a in A:
        if len(st) == 0 or st[-1] == a:
            st.append(a)
        else:
            st.pop()
    
    # there is no leader
    if len(st) == 0:
        return 0
    
    candidate = st[-1]
    leader_count = 0
    for a in A:
        if candidate == a:
            leader_count += 1
    
    # there is no leader
    if leader_count <= len(A) // 2:
        return 0

    leader = candidate
    
    # dp[x] : the number of leaders in A[0...x]
    dp = []
    cur_count = 0
    for a in A:
        if a == leader:
            cur_count += 1
        dp.append(cur_count)
    #print(dp)

    # N = len(A) - 1
    # head = [0...x], tail = [x+1...N]
    # the number of leaders in head : dp[x]
    # the number of leaders in tail : leader_count - dp[x]
    ans = 0
    for i in range(len(A) - 1):
        if dp[i] > (i + 1) // 2 and (leader_count - dp[i]) > (len(A) - 1 - i) // 2:
            ans += 1

    return ans