[알고리즘] Moore's voting algorithm

leetcode의 169. Majority Element 문제를 풀다가 알게된 알고리즘입니다.

 

이 알고리즘은 처음 들어봐서 공부하고 정리했습니다.

 

 

1. 배경

문제를 간단하게 요약하면,

array 에 (array의 length // 2) 번 넘게 나타나는 원소를 찾는 것입니다.

 

처음에는 sort를 이용하려고 했는데, O(nlogn) 시간복잡도가 생기고 공간은 O(1) 를 사용하게 됩니다.

하지만 문제 맨 마지막 줄에 선형 시간 + 공간 O(1) 만 사용해서 풀 수 있다는 글이 있었습니다.

 

 

도저히 모르겠어서 결국 해답을 봤고, Moore's voting 알고리즘을 알게 되었습니다.

 

 

2. 알고리즘 

이 알고리즘은 stream algorithim 입니다.(데이터 스트림을 처리하는 알고리즘)

 

배열에 중복되는 데이터가 과반수 이상이 있어야 동작합니다.

 

 

fun findMajorityElement(nums: IntArray): Int? {
    var candidate: Int? = null
    var count = 0

    // 1️⃣ 후보 선정 단계
    // 핵심 로직
    for (num in nums) {
        if (count == 0) {
            candidate = num
        }
        
        
        count += if (num == candidate) 1 else -1
    }

    // 2️⃣ 검증 단계 (필요한 경우)
    val majorityCount = nums.size / 2
    return if (nums.count { it == candidate } > majorityCount) candidate else null
}

fun main() {
    val nums = intArrayOf(2, 2, 1, 1, 1, 2, 2)
    println(findMajorityElement(nums)) // 출력: 2
}

(gpt가 구현해준 코드입니다. gpt 좋네요.)

 

이고, 최종으로 나오는 element가 절반 넘게 등장하는 값이 됩니다.