[Codility] 8.1 Dominator

Dominator

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

leader를 구하는 것과 동일한 방식으로 접근하면 된다.

1. 스택에 숫자를 넣는다.
   1.1 스택의 top과 넣으려는 수가 다르면 top을 제거(remove pair)한다.
   1.2 같다면 그대로 스택에 push 한다.
2. 스택의 top은 leader(dominator)의 후보값이다.
   2.1 스택이 비어있다면 존재하지 않는다.

def solution(A):
    st = []  # empty stack
    
    for x in A:
        # stack is empty, then just push the item
        if len(st) == 0:
            st.append(x)
        # compare the item and top of the stack
        else:
            if st[-1] != x:
                del st[-1]  # remove the pair
            else:
                st.append(x)  # push the item
    
    # 스택이 비어있으면, dominator가 없다. -1을 리턴
    if len(st) == 0:
        return -1
        
    # 후보값 저장
    candidate = st[-1]
    
    # dominator가 없다면, input범위 밖의 수로 설정
    dominator = 9999999999
    
    # 후보값이 배열에 얼마나 많이 있는지 counting
    cnt = 0
    for x in A:
        if x == candidate:
            cnt += 1
    
    # 후보값이 dominator가 되려면, 그 빈도수가 N/2보다 많아야 한다
    if cnt > len(A) // 2:
        dominator = candidate
    
    # 후보값의 빈도수가 모자라 dominator가 되지 않는경우
    if dominator == 9999999999:
        return -1
        
    # dominator와 같은 수의 인덱스 아무거나 return    
    ret = -1
    for i in range(len(A)):
        if A[i] == dominator:
            return i
    
    # 사실 여기까지 코드가 오지 않는다
    return ret