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

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

Dominator coding task - Learn to Code - Codility

문제 내용

N개의 배열 A가 주어질 때, 배열 A의 지배자를 찾아내시오. 지배자는 각 배열 요소의 값이 배열의 반 넘게 발생하면, 이 값은 배열 A의 지배자라고 할 수 있다.

 

예를 들어, A = [3, 4, 3, 2, 3, -1 ,3 ,3]일 때,

3이 총 5번으로 8개중에 반 넘게 등장하므로, 지배자는 3이고, 3을 가지고 있는 index 0, 2, 4, 6, 7중에 아무거나 하나를 return하면 된다.

제한 사항

• N은 0~100,000
• A의 각 요소는 -2,147,483,648~2,147,483,648

코드

def solution(A):
    
    check = {}
    for a in A:
        if not a in check:
            check[a] = 1
        else :
            check[a] += 1

    m = float("-inf")
    for k,v in check.items():
        if m < v:
            m = v
            i = k
    
    if m > len(A)/2:
        return A.index(i)
    else :
        return -1

해설

딕셔너리에 요소 별 값들을 key로 넣으면서 value에는 count를 합니다.

count한 값중에 제일 큰 값의 key를 찾아 냅니다.

 

이 때, count한 값이 반이 넘지 못하면 -1을 return하고 반을 넘는 경우에는 배열 A에서 value가 있는 index를 찾아서 return합니다.