C# 프로그래밍 기초 실습 전자책

C# / .NET 알고리즘과 퀴즈
본 알고리즘 퀴즈 문제는 C#/.NET 개발자를 위한 알고리즘 인터뷰 혹은 C# 프로그래밍을 통한
문제 해결 알고리즘을 연구해 보는데 도움이 되고자 작성되었습니다.


퀴즈 질문


예상답변/설명

Boyer-Moore Majority Vote Algorithm을 사용. 순차적으로 배열을 읽으면서 같은 요소가 나오면 카운터에 +1을, 다른 요소가 나오면 -1을 해주고, 만약 카운터가 0이 되면 다른 요소로 교체하여 위의 과정을 반복한다. 한 배열요소가 절반이 넘기 때문에, 모든 배열요소를 처리한 후에 답이 되는 요소에 대해서는 항상 카운터가 1보다 크게 남게 된다.

class FindMajorityInArray
{
    public void RunTest()
    {
        int[] A = { 3, 2, 2, 3, 2, 1, 2 }; 
        int majority = FindMajorityElement(A);
        Console.WriteLine(majority);
    }

    int FindMajorityElement(int[] A)
    {
        int current = 0;
        int counter = 0;

        for (int i = 0; i < A.Length; i++)
        {
            if (counter == 0)
            {
                current = A[i];
                counter = 1;
            }
            else
            {
                if (A[i] == current)
                {
                    counter++;
                }
                else
                {
                    counter--;
                }
            }
        }

        return current;
    }
}