크기가 n인 배열이 주어졌을 때, 과반수 요소(Majority Element)를 찾아야 하는 문제가 있습니다. 과반수 요소란 배열 전체 길이의 절반인 n/2번보다 더 많이 등장하는 요소를 의미합니다.
해결 방법
가장 효율적인 접근 방식은 해시 객체(맵)를 활용해 각 요소의 등장 횟수를 기록하는 것입니다. 요소를 하나씩 순회하면서 개수를 세고, 그 개수가 n/2(내림 처리)를 초과하는 순간 해당 요소를 즉시 반환하면 됩니다. 이렇게 하면 조기 반환(early return)이 가능해 불필요한 순회를 줄일 수 있습니다.
예제 코드
const arr = [2, 4, 2, 2, 2, 4, 6, 2, 5, 2];
const majorityElement = (arr = []) => {
const threshold = Math.floor(arr.length / 2);
const map = {};
for (let i = 0; i < arr.length; i++) {
const value = arr[i];
map[value] = map[value] + 1 || 1;
if (map[value] > threshold) {
return value;
}
}
return false;
};
console.log(majorityElement(arr));코드 설명
1. 임계값 계산: Math.floor(arr.length / 2)를 사용해 과반수 판정 기준이 되는 임계값을 구합니다. 배열 길이가 10이므로 임계값은 5가 됩니다.
2. 등장 횟수 기록: 객체 map에 각 요소를 키로 저장하고, 등장할 때마다 개수를 1씩 증가시킵니다. map[value] + 1 || 1 표현식은 해당 요소가 처음 등장했을 때(즉, undefined + 1이 NaN이 될 때) 1로 초기화해 주는 역할을 합니다.
3. 조기 반환: 특정 요소의 개수가 임계값을 초과하는 즉시 그 값을 반환하므로, 배열 전체를 끝까지 순회하지 않아도 되는 경우가 많습니다.
4. 과반수 요소가 없는 경우: 반복문이 끝날 때까지 조건을 만족하는 요소가 없다면 false를 반환합니다.
실행 결과
콘솔에 출력되는 결과는 다음과 같습니다.
2
위 예제에서 숫자 2는 총 6번 등장하며, 이는 임계값인 5보다 크기 때문에 과반수 요소로 판정됩니다.
시간 복잡도
이 알고리즘의 시간 복잡도는 O(n)이고, 공간 복잡도 역시 최악의 경우 모든 요소가 서로 다를 때 O(n)입니다. 배열을 한 번만 순회하면 되기 때문에 매우 효율적이며, 실무에서도 널리 사용되는 패턴입니다.