[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]