[Python] 8.1. Dominator

https://app.codility.com/demo/results/trainingKJKX8S-C3B/

Test results - Codility

---

Task Score

100%

Correctness

100%

Performance

100%

Detected time complexity

O(N * log(N)) or O(N)

def solution(A):

    n = len(A)
    stack = []
    
    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+1:
        return A.index(stack[-1])
    else:
        return -1

 

문제를 푸는데 도움이 된 테스트 케이스

[] [0] [1,1] [1,2] [1,2,3] [2,1,1] [1,1,2,2] [2,1,1,1] [1,1,2,2,2]