Lesson 8: Leader → Equil Leader

문제

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

EquiLeader coding task - Learn to Code - Codility

---

문제 풀이

Dominator 문제와는 다르게, 각 구간 별로 left, right의 leader가 일치하는지 확인하는 문제이다.

주어진 예시의 경우 4, 3, 4, 4, 4, 2이다. 리스트의 앞에서 부터 구간을 left, right로 나누게 되면 다음과 같다.

	left	right
Phase 1	4	3	4	4	4	2
	left		right
Phase 2	4	3	4	4	4	2
	left			right
Phase 3	4	3	4	4	4	2
	left				right
Phase 4	4	3	4	4	4	2
	left					right
Phase 5	4	3	4	4	4	2

 

• 1 단계에서는 left leader는 4이고, right leader는 4이기 때문에 경우의 수에 포함한다.

• 2 단계는 left leader는 없고, right leader는 4이기 때문에 경우의 수에 포함하지 않는다.

• 3 단계는 left leader는 4이고, right leader는 4이기 때문에 경우의 수에 포함한다.

• 4, 5 단계는 left leader와 right leader가 다르기 때문에 경우의 수에 포함하지 않는다.

---

코드

def solution(A):
    left, right = {}, {}
    left_length, right_length = 0, len(A)
    left_leader = 0
    cnt, left_cnt = 0, 0

    for num in A:
        try:
            right[num] += 1
        except KeyError:
            right[num] = 1

    for i in range(len(A)):
        right[A[i]] -= 1
        right_length -= 1

        try:
            left[A[i]] += 1
        except KeyError:
            left[A[i]] = 1

        left_length += 1

        if left[A[i]] > left_cnt:
            left_leader = A[i]
            left_cnt = left[A[i]]

        if right[left_leader] > right_length // 2 and left_cnt > left_length // 2:
            cnt += 1

    return cnt

• right에 각각의 값들을 카운트한다.

• right에 카운트된 값을 left로 옮겨주어 각각의 leader를 비교하여 답을 찾을 수 있다.