[Codility] 8. Leader (Dominator, EquiLeader)

Leader

리더: 과반초과(more than 2/n)으로 등장한 수를 찾기→ 최대 하나, 없을수있음

 

리더 찾는 기본 코드

#Lesson8_Leader
#O(n)

def goldenLeader(A):
    n=len(A)
    #제일 많이 등장하는 수 찾기(stack알고리즘과 유사)
    size=0
    for k in range(n):
        if size==0:
            size+=1
            value=A[k]
        else:
            if value!=A[k]:
                size-=1
            else:
                size+=1
    #제일 많이 등장한 수가 과반초과인지 확인
    candidate=-1
    if size>0:
        candidate=value
    leader=-1
    count=0
    for k in range(n):
        if A[k]==candidate:
            count+=1
    if count>n//2:
        leader=candidate
    return leader

 

Dominator

Task description

The dominator of array A is the value that occurs in more than half of the elements of A.

Write a func that, given an array A consisting of N integers, returns index of any element of array A in which the dominator of A occurs. The function should return −1 if array A does not have a dominator.

 

배열 A의 dominator는 A의 요소 중 절반 이상에서 발생하는 값입니다.

N개의 정수로 구성된 배열 A가 주어졌을 때, A의 dominator가 발생하는 배열 A의 요소의 인덱스를 반환하는 함수를 작성합니다. 배열 A에 dominator가 없으면 함수는 -1을 반환해야 합니다.

def solution(A):
    n = len(A)
    #가장 많이 나온 수 찾기
    size = 0
    for k in range(n):
        if (size == 0):
            size += 1
            value = A[k]
        else:
            if (value != A[k]):
                size -= 1
            else:
                size += 1

    candidate = -1
    if (size > 0):
        candidate = value

    idx = []
    for k in range(n):
        if (A[k] == candidate):
            idx.append(k)

    if (len(idx) > n // 2):
        return idx[0]
    else:
        return -1

※  배열을 return 하는게 아닌, 그 중 하나 return하는 거라 idx[0]으로 함!

 

EquiLeader

Task description

The leader of this array is the value that occurs in more than half of the elements of A. An equi leader is an index S such that 0 ≤ S < N − 1 and two sequences A[0], A[1], ..., A[S] and A[S + 1], A[S + 2], ..., A[N − 1] have leaders of the same value.

Write a func that, given a non-empty array A consisting of N integers, returns the number of equi leaders.

 

이 배열의 leader는 A의 원소의 절반 이상에서 나타나는 값입니다. equi leader는 0 ≤ S < N - 1이고 두 개의 시퀀스 A[0], A[1], ..., A[S + 1], A[S + 2], ..., A[N - 1]이 같은 값의 리더를 갖는 인덱스 S입니다.

N개의 정수로 구성된 비어 있지 않은 배열 A가 주어졌을 때 equi leaders의 수를 반환하는 함수를 작성합니다.

 

def solution(A):
    # leader 찾기
    size = 0
    for k in range(len(A)):
        if (size == 0):
            size += 1
            candidate = A[k]
        else:
            if (candidate != A[k]):
                size -= 1
            else:
                size += 1
    if size <= 0:
        return 0

    # prefix sum ->이 지점에서 끊으면 왼쪽,오른쪽 leader 갯수 알 수 있게됨
    idx = [0]
    for k in range(len(A)):
        offset = 0
        if (A[k] == candidate):
            offset = 1
        idx.append(idx[-1] + offset)
        # 해당 숫자(A[k])가 leader가 맞으면 offset=1이므로 개수 추가된 상태로 idx 리스트에 값 저장됨
        # idx엔 왼쪽 leader 갯수 저장됨
    res = 0
`   # 여기서 idx[-1]은 총 leader 갯수
    if (idx[-1] > len(A) // 2):
        for i, k in enumerate(idx[1:]):
            if k > (i + 1) // 2 and idx[-1] - k > (len(A) - (i + 1)) // 2:  # 왼쪽, 오른쪽 각각 체크
                res += 1
    return res