코드노예

배열 혹은 리스트 등에서 과반수가 넘는 원소를 찾는 알고리즘입니다.

가장 기본적인 접근법은 각 원소별로 리스트를 모두 체크해서 해당 원소가 나오는 숫자를 세고, 과반수가 넘는지 체크하는 방법이 있습니다.

def find(nums):
    minCnt = len(nums) // 2
    for num in nums:
        cnt = sum(1 for elem in nums if elem == num)
        if cnt > minCnt:
            return num

시간 복잡도는 O(n^2) 이며, 공간 복잡도는 O(1) 입니다.

수행시간을 줄이기 위해서는 Dictionary 를 사용하는 방법이 있습니다.

def find(nums):
    dict = collections.Counter(nums)
    return max(dict.keys(), key=dict.get)

시간 복잡도는 O(n) 이며, 공간 복잡도는 O(n) 입니다.

그리고 데이터를 정렬해서 가운데 있는 원소를 뽑아내는 방법도 있습니다.

과반수 이상 존재하는 원소는 정렬시 반드시 중간 인덱스에 존재하기 때문입니다.

def find(nums):
    nums.sort()
    return nums[len(nums)//2]

이 경우 시간 복잡도는 O(n log n) 이며, 공간 복잡도는 O(1) 입니다.

그 외에 분할정복 방법으로도 찾을 수가 있습니다.

분할정복은 분할을 통해서 선택된 양쪽의 값이 같은 경우 해당 값을 선택하고,

다를 경우 분할된 셋에 각각 선택된 값의 숫자를 카운트하여 많은 쪽을 택하면 됩니다.

이 경우 시간 복잡도는 O(n log n) 이며, 공간 복잡도는 O(log n) 입니다.

마지막으로 Boyer-Moore 과반수 투표 알고리즘을 소개합니다.

알고리즘은 다음과 같습니다.

가장 많이 나올 후보 원소를 선택하고,

원소들을 순회하며 후보와 같은 값일 경우 카운트를 올리고,

다른 값일 경우 카운트를 차감합니다. 

카운트가 0이 되면 새로 후보를 선택하고, 순회하며 카운트를 반복합니다.

과반수가 넘는 원소는 카운트가 0보다 크거나, 최종적으로 선택되게 됩니다.

def find(nums):
    cnt = 0
    candidate = None
    
    for num in nums:
        if cnt == 0:
            candidate = num
        cnt += (1 if num == candidate else -1)

    return candidate

시간 복잡도는 O(n) 이며, 공간 복잡도는 O(1) 입니다.