[Codility] 8. Leader

Leader of sequence

길이가 N인 수열에서, N/2개가 넘는 수가 똑같은 값인 원소가 존재할 때, 그 값을 leader of sequence 또는 leader라 한다.

예1) [6, 8, 4, 6, 8, 6, 6]의 경우, leader = 6이다. (그림)
예2) [1, 2, 3, 4, 5, 6, 7]의 경우, leader는 존재하지 않는다.

그렇다면 leader는 어떻게 구할까? 당장 떠오르는 naive한 방법은 $O(N^2)$으로 모두 탐색하는 방법이다. 그런데 너무 비효율적이다.

방법1. 정렬

(수열의 모든 수는 음이 아닌 수라고 가정한다.)
leader는 N/2개보다 많이 존재하므로, 수열을 정렬하면 중앙값이 당연히 leader의 수와 같아진다. 이를 이용한 알고리즘이다.

1. 수열을 정렬한다. O(NlogN)
   1.1 정렬된 수열의 중앙값은 leader의 후보가 된다.
2. 후보값이 n/2개 보다 많다면 후보는 leader가 된다. O(N)

def find_leader(L):
	N = len(L)
    leader = -1 # leader가 없다면 -1을 return
    L.sort()    # sorting - O(NlogN)
    candidate = L[N // 2] # 중앙값은 leader의 후보
    count = 0   # 후보값의 개수
    
    # linear search - O(N)
    # 후보값이 수열에 몇개 존재하는지 counting
    for i in range(N):
    	if L[i] == candidate:
        	count += 1
    
    # 후보값이 N/2개 보다 많다면 leader이다.
    if count > N // 2:
    	leader = candidate
    
    return leader

방법2. 스택

(수열의 모든 수는 음이 아닌 수라고 가정한다.)
leader는 가장 많이 존재하는 수이다. 그리고 서로 다른 2개의 수를 제거하면 남은 N-2개의 수열의 leader와 동일한 leader를 갖는다. 왜냐하면 제거한 2개의 수 중 하나가 leader여도, 남은 N-2개의 수열에서 leader는 (N-2)/2개 보다 많이 존재하기 때문이다.

그렇다면 서로 다른 두개의 수를 어떻게 제거할 것인가? -> 스택!

1. 스택에 순서대로 수를 push한다.
2. 스택의 top에 있는 2개의 수를 비교한다.
   2.1 2개의 수가 서로 다르면, 2개 모두 스택에서 제거한다.

def find_leader(L):
	N = len(L)
    size = 0
    for i in range(N):
    	# 스택이 비어있다면, value: top of the stack
    	if size == 0:
        	size += 1
            	value = L[i]
        else:
        	# 스택이 비어있지 않고, top과 현재 수가 다르면
           	# 현재 수를 스택에 넣지안고, top을 제거
        	if value != L[i]:
            	size -= 1
           	
            	# 스택에 현재 수 삽입
            	else:
            	size += 1
	
    candidate = -1
    leader = -1
    count = 0
    
    # 서로다른 쌍 제거후에도 스택이 남아있다면, top이 후보값
    if size > 0:
    	candidate = value  
    
    # 후보값이 N/2개보다 많은지 확인
    for i in range(N):
    	if L[i] == candidate:
        	count += 1
    if count > N // 2:
    	leader = candidate
    
    return leader