(코딜리티) Lesson 8. [Leader] : EquiLeader - python

문제 : app.codility.com/programmers/lessons/8-leader/equi_leader/

EquiLeader coding task - Learn to Code - Codility

문제 내용

비어 있지 않은 N개의 배열 A가 주어질 때, S는 0 <= S < N-1라고 할 때, A[0], A[1], ... , A[S] and A[S+1], A[S+2], ... , A[N-1]인 두 배열에서 동등한 지배자인 경우의 수를 return하시오.

 

예를 들어, A = [4, 3, 4, 4, 4, 2] 인 경우,

S = 0일 때, [4] 와 [3, 4, 4, 4, 2]는 둘 다 4를 지배자로 가진다.

S = 2일 때, [4, 3, 4] 와 [4, 4, 2]는 둘 다 4를 지배자로 가진다.

 

따라서, 경우의 수는 2개이므로, 2를 return한다.

제한 사항

• N은 1~100,000
• A의 각요소는 -1,000,000,000~1,000,000,000

코드

def solution(A):

    count = 0

    right_dict = {}
    right_len = len(A)
    for a in A:
        if a in right_dict:
            right_dict[a] += 1
        else:
            right_dict[a] = 1
    
    left_leader = 0
    left_leader_count = 0
    left_dict = {}
    left_len = 0

    for a in A:
 
        right_dict[a] -= 1
        right_len -= 1

        if a in left_dict:
            left_dict[a] += 1
        else:
            left_dict[a] = 1
        left_len += 1
        
        if left_dict[a] > left_leader_count:
            left_leader = a
            left_leader_count = left_dict[a]
        
        if left_leader_count > left_len/2 and right_dict[left_leader] > right_len/2:
            count += 1

    return count

해설

제일 처음 처음 전체 값을 오른 쪽 dictionary에 넣어 빈도 수를 만든 후,

for문을 하나씩 돌면서 오른쪽 dictionary는 빼고, 왼쪽 dictionary에 추가합니다.

추가하면서, 좌측에서 제일 큰 값을 우측에서도 도출해 내고, 둘다 전체 중에 반을 넘는 지 확인하면, count를 하나씩 늘립니다.