분할정복 사용해 배열에서 과반수 요소 찾기

정수 배열에서 과반보다 많이 존재하는 요소를 찾는 알고리즘이다. 분할 정복을 이용하면 O(n log n)의 시간에 해결할 수 있다. 배열에 과반수 요소가 있다고 가정한다. 있을 지 없을지 모른다고 할때는 반복문을 한번 돌리면서 결과로 나온 숫자가 몇번 나오는지 보면 된다.
메인 아이디어는 배열을 계속 반으로 쪼개면서(logn) 양쪽 배열 각각의 과반수 원소를 찾는다(left, right). 배열을 다시 합치고 그 중 각 배열에서 더 많이 나온 요소가 전체 배열의 과반수 요소가 된다.
https://leetcode.com/problems/majority-element/
https://www.geeksforgeeks.org/majority-element/

public class Main
{/* 배열에서 과반수 요소를 찾아 리턴하는 함수
분할 정복을 사용해 배열을 반씩 나눠서 각 왼, 오른쪽 배열의
과반수 요소를 찾고 비교한다. */
    public static int maj(int[] arr, int start, int end)
    {
        if (start == end) // 배열에 원소가 하나일때 
        {
            return arr[start];
        }
        int mid = (start + end) / 2;
        int left = maj(arr, start, mid); // 왼쪽 배열의 과반수 요소
        int right = maj(arr, mid+1, end);
        if (left == right) // 양쪽의 과반수 원소가 같을때
            return left;
        return count(arr, start, mid, left) > count(arr, mid+1, end, right) ? left : right; // 양쪽 배열의 과반수 요소(left, right)가
            // 각 배열에서 몇번 나오는지 세고 많이 나온것이 전체 배열의 과반수 요소
    }
    
    public static int count(int[] arr, int start, int end, int majNum)
    {
        int res = 0;
        for (int i=start; i<end; i++)
        {
            if (arr[i] == majNum)
                res++;
        }
        return res;
    }
    
    
    public static void main(String[] args)
    {
        int[] arr = {2,2,2,4,5,7,3,1,6,2,2,2,2};
        System.out.println(maj(arr, 0, arr.length-1));
    }
}