LeetCode 169 - Majority Element (Easy)

 

최근 몇달동안 LeetCode 문제풀이를 못했는데,

올해에는 재미와 성취감을 위해 시간 날때마다 짬내서 간단한 문제를 하나씩 다시 풀어보려고합니다. 😄

 

💡 문제

LeetCode - 169번

 

🎯 풀이 과정

n 크기의 배열이 주어질 때, 과반수 이상의 요소를 찾는 문제입니다.

해시맵을 이용해서 구현할수도 있지만 좀 더 최적화된 방법으로 해결할 수도 있습니다.

 

요구조건에 의해 과반수를 차지하는 요소가 반드시 존재한다는 것이 보장되기 때문에

보이어-무어 과반수 투표 알고리즘 을 활용하면 O(n) 의 시간복잡도와 O(1) 의 공간 복잡도를 가지는 풀이를 만들 수 있습니다.

 

이 알고리즘을 간단히 풀어보자면, 길이 n 을 가지는 배열 A 에서 과반수를 차지하는 요소 a가 [n/2 + 1] 개 있을 경우에

나머지 요소들의 개수의 합은 [n - (n/2 + 1)] 이며 이는 절대 [n/2 + 1] 보다 클 수 없습니다.

 

따라서 이 점을 활용해 major 와 count 를 변수로 두고 배열을 순회하면서

count 가 0일때는 해당 요소를 major로, 같은 종류의 요소를 발견하면 +1, 다르다면 -1 을 하면

최종적으로 남아있는 major 가 과반 이상의 요소가 됩니다.

 

보다 자세한 내용은 다음 블로그를 참조하면 좋을 것 같습니다.

Boyer-Moore 과반수 투표 알고리즘

Boyer-Moore 과반수 투표 알고리즘

 

👨‍💻 코드

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    let major = null
    let count = 0

    for (let num of nums) {
        if (count === 0) {
            major = num
        }

        count += (major === num ? 1 : -1)
    }

    return major
};