[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