[코딜리티] 파이썬 _ Dominator

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

Dominator coding task - Learn to Code - Codility

 

문제번역 : 리스트의 길이의 절반이상을 차지하는 원소가 있다면, 그 원소가 등장하는 아무 인덱스를 리턴하는것

 

문제풀이 :

• 리스트의 절반이상을 차지하는 원소가 있다면, 즉 dominator가 존재한다면 정렬했을때 무조건 중심에 위치하게 될것임
  • 다만, 중심에 있는 원소가 dominator의 후보가 되는것이지 무조건 dominator라는것은 아니다. 
  • 따라서 한번더 확인해줘야하는데 나는 bisect모듈을 활용해서 해당 원소의 갯수를 찾아주었다.
• 만약 가장작은원소가 dominator라고 한다면 맨앞에서부터 시작해도 반이상을 차지하려면 무조건 중간은 넘기게되기 때문이다.
• 이때 짝수인지 홀수인지에 따라서 조금 다르게 해주면 된다.

 

정답코드 :

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    # write your code in Python 3.6
    if not A:
        return -1
    
    n = len(A)
    
    mid = n // 2
    
    a = sorted(A)
    d = None  # 도미네이터의 후보

    if n % 2 == 0:
        if a[mid] == a[mid-1]:
            d = a[mid]
    else:
        d = a[mid]
    
    if not d:
        return -1
    
    from bisect import bisect_left, bisect_right

    l_idx = bisect_left(a, d)
    r_idx = bisect_right(a, d)
    #print(r_idx, l_idx)

    if r_idx-l_idx >= (n//2)+1:
        return A.index(d)
    else:
        return -1