1. Problem
Assume you have an array A[1...N] of n elements.
A majority element of A is any element occurring in more than n/2 positions
(so if n = 6 or n = 7, any majority elements will occur in at least 4 positions).
For example, the array
3, 3, 4, 2, 4, 4, 2, 4, 4
has a majority element (4), whereas the array
3, 3, 4, 3, 4, 4, 2, 4
does not.
Assume that elements cannot be ordered or sorted. but can be compared for quality. Write a
program that finds a majority element in A. If there is no majority element, your program
should indicate this. Design an efficient divide and conquer algorithm to find the majority
element. Aim for an algorithm that does O(nlgn) equality comparisons between the elements.


이게 무슨 뜻인지 모르겠어.

내가 대충 해석한 내용을 말하자면

추정하건데 당신은 n개의 원소들을 가진 배열 A를 갖고 있을 것이다.
A 배열에서 가장 많은 원소는 ~~~~모르겠고
예를 들면 배열 3,3,4,2,4,4,2,4,4 는 가장 많은 원소로 4가 있고
반면에 배열 3,3,4,3,4,4,2,4는 그렇지 않다.
추정하건데 원소들은 순서대로 혹은 정렬되어 있지 않을 것이다.
하지만 같은지 비교할 수 있다.
A배열에서 가장 많은 원소를 찾는 프로그램을 짜라.
만약 거기에 가장 많은 원소가 없다면, 당신의 프로그램은 그것을 인지할 수 있도록 해라.
효과적으로 나누도록 디자인하고 가장 많은 요소를 찾는 알고리즘을 정복해라.
알고리즘의 목표는 시간복잡도가 O(n log n)이 되게 하는 것이다.


여기서 첫번째 예에서 4가 가장 많은 원소인 것은 알겠는데
두번째 예에서 3, 3, 4, 3, 4, 4, 2, 4 에서도 4가 4개, 3이 3개니까 4가 가장 많은 원소로
되는거 아닌가?
내가 해석 못한 부분에 이 비밀이 숨겨져있는거야?