[codility] Lesson 8. Leader - Dominator

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

Dominator coding task - Learn to Code - Codility

 

 

• N개의 정수로 구성된 배열A가 주어질 때
• 배열 A의 Dominator는 A의 요소 중 절반 이상에서 발생하는 값이다.
• A[0] = 3 A[1] = 4 A[2] = 3 A[3] = 2 A[4] = 3 A[5] = -1 A[6] = 3 A[7] = 3
• 0, 2, 4, 6, 7번째 총 5개의 인덱스에서 값으로 3을 가지고 있다.
• 8개의 정수로 구성된 배열 A에서 5는 배열의 절반 이상이기 때문에 3은 Dominator
• Dominator의 값을 출력하고, 없으면 -1 출력
• O(N*log(N)) or O(N)

 

def solution(A):
    if not A:
        return -1
    dict = {}

    for x in range(len(A)):
        dict[A[x]] = dict.get(A[x], 0) + 1
        if dict[A[x]] > len(A)//2:
            return x
    return -1