[Python] Leader

https://codility.com/media/train/6-Leader.pdf

 

---

Leader는 크기 N인 배열A 에서 과반수 이상 (N//2+1) 의 갯수를 가지고 있는 요소를 말한다. 

Leader를 조사하는 방법을 아래와 같이 정리하였다.

 

 

1. Sorting

정렬 후 중앙값의 카운트를 계산한다.

카운트가 n//2 보다 크다면 Leader에 해당한다.

Detected time complexity O(N * log(N))

def solution(A):
    n = len(A)
    s_A = sorted(A)
    leader = None
    
    count = 0
    for i in range(n):
        if s_A[i] == s_A[n//2]:
            count += 1
    if count > n // 2:
        leader = s_A[n//2]
        
    return leader

 

2. Stack

stack을 만들고 첫번째 Element를 push한다. 두번째 Element 부터 stack의 peak와 비교해서 다르면 pop, 같으면 push한다.

최종적으로 stack의 peak가 leader의 후보가 되며, 후보의 카운트가 n//2 보다 크다면 leader에 해당한다.

Detected time complexity O(N)

def solution(A):
    n = len(A)
    stack = []
    leader = None
    
    for a in A:
        if not stack:
            stack.append(a)
        else:
            if stack[-1] != a:
                stack.pop()
            else:
                stack.append(a)

    cnt = 0
    for a in A:
        if stack and a == stack[-1]:
            cnt += 1

    if cnt > n // 2:
        leader = stack[-1]

    return leader