문제 정의
반복되는 값이 포함된 숫자 배열을 입력받아, 배열 전체 길이의 절반(n/2)보다 많이 등장하는 요소, 즉 '다수 요소(majority element)'가 존재하는지 판별하는 자바스크립트 함수를 작성해 보겠습니다. 다수 요소가 존재하면 true를, 존재하지 않으면 false를 반환합니다.
예를 들어, 배열 [12, 5, 67, 12, 4, 12, 4, 12, 6, 12, 12]에서 숫자 12는 총 11개 요소 중 6번 등장하므로 과반수(5.5회)보다 많습니다. 반면 두 번째 예시 배열에는 그러한 요소가 없으므로 결과는 false가 됩니다.
구현 코드
이 문제는 보이어-무어 투표 알고리즘(Boyer–Moore Voting Algorithm) 개념을 활용하면 시간 복잡도 O(n), 공간 복잡도 O(1)로 효율적으로 해결할 수 있습니다. 코드는 두 단계로 구성됩니다.
- 1단계: 배열을 한 번 순회하며 다수 요소의 '후보'를 결정합니다.
- 2단계: 후보가 실제로 과반수 이상 등장했는지 최종 검증합니다.
const arr = [12, 5, 67, 12, 4, 12, 4, 12, 6, 12, 12];
const arr1 = [3, 565, 7, 23, 87, 23, 3, 65, 1, 3, 6, 7];
const findMajority = arr => {
let maxChar = -Infinity, maxCount = 1;
// 1단계: 다수 요소의 후보를 결정하는 루프
for(let i = 0; i < arr.length; i++){
if(maxChar !== arr[i]){
if(maxCount === 1){
maxChar = arr[i];
} else {
maxCount--;
};
} else {
maxCount++;
};
};
// 2단계: 후보가 실제로 다수 요소인지 검증하는 루프
const count = arr.reduce((acc, val) => maxChar === val ? ++acc : acc, 0);
return count > arr.length / 2;
};
console.log(findMajority(arr));
console.log(findMajority(arr1));
실행 결과
콘솔 출력 결과는 다음과 같습니다.
true
false
동작 원리 설명
첫 번째 루프에서는 서로 다른 값을 만날 때마다 카운트(maxCount)를 감소시키고, 같은 값을 만나면 증가시킵니다. 카운트가 1이 되면 현재 요소를 새로운 후보로 지정합니다. 이 방식 덕분에 진짜 다수 요소가 있다면 마지막까지 후보 자리에 남게 됩니다.
두 번째 루프에서는 reduce() 메서드를 사용해 해당 후보가 배열에 실제로 몇 번 등장하는지 계산한 뒤, 그 횟수가 배열 길이의 절반보다 큰지 비교하여 최종 boolean 값을 반환합니다. 이처럼 검증 단계를 거치기 때문에 다수 요소가 없는 경우에도 정확하게 false를 반환할 수 있습니다.