다수 원소(Majority Element) 찾기

여기 갈비탕 고기 많이 준다. (을지로 우촌)

어떤 배열에 과반수 이상 존재하는 원소가 있다면 그 원소를 찾고 싶다. 어떻게 찾을 수 있을까? 여기서 직접 코딩 해보자.

1. 무작정 루프 돌리기

가장 직관적인 방법으로, 이중 반복 하므로 시간복잡도는 O(n²) 이고 공간복잡도는 O(1)이다.

2. 정렬해서 찾기

정렬하고 차례대로 현재 원소가 과반수를 넘었는지 확인하는 방법이다. 시간복잡도는 O(nlogn), 공간복잡도는 O(1)이다. 1번 방법보다 더 효율이 좋다.

3. 해쉬맵 이용하기

반복문을 돌면서 <원소, 횟수>를 기록해나간다. 횟수가 과반수를 넘었다면 바로 그 원소가 내가 찾는 원소이다. 시간복잡도는 O(n), 시간복잡도는 O(n) 이다. 메모리 효율을 포기하고 속도를 높혔다.

from collections import Counter
for t in range(int(input())):
    _ = input()
    nums = list(map(int, input().split()))
    c = Counter()
    res = -1
    for num in nums:
        c[num] += 1
        if c[num] > len(nums)//2:
            res = num
            break
    print(res)

4. 더 나은 방법

3번 방법이 최선인가? ‘Boyer-Moore majority vote algorithm’ 을 이용하는 방법이 있다. 결론부터 말하면 시간복잡도 O(n), 공간복잡도 O(1)이다. 아래 코드에서 find_candidate()가 핵심이라고 볼 수 있다. 이 함수는 다수 원소가 있다는 가정하에 정상적으로 동작하기 때문에 is_majority()로 검증이 필요하다.

간단하게 설명하면, ‘다수 원소의 출현횟수의 총합은 나머지 원소의 출현횟수보다 많다’라는 원리를 이용한 것이다.

def find_candidate(nums: list)->int:
    cand = nums[0]
    cnt = 1
    for i in range(1, len(nums)):
        if nums[i] == cand:
            cnt += 1
        else:
            cnt -= 1
            if cnt == 0:
                cand = nums[i]
                cnt = 1
    return cand
def is_majority(nums: list, candidate: int)->bool:
    cnt = 0
    for num in nums:
        if num == candidate:
           cnt += 1
           if cnt > len(nums)//2:
               return True
    return False
    
    
for t in range(int(input())):
    _ = input()
    nums = list(map(int, input().split()))
    candidate = find_candidate(nums)
    if is_majority(nums, candidate):
        print(candidate)
    else:
        print(-1)

실무에서 쓰일 만한 내용일까 생각해봤다. 과반수 이상을 차지하는 무언가를 찾아야 할만 상황이 무엇이 있을까? 땅따먹기 게임에서 절반이상을 먹으면 게임이 종료되는 상황에 쓸 수 있을 것 같다. ㅋㅋㅋ