2.majority

[문제]

어떤 포털 사이트에서 특정 시간(time window)동안 수집된 전체 개의 단어(word) 기록이 있다. 이 중에서 과반(반을 넘는)인 $n / 2 + 1$회 이상 나타난 단어를 “인기 검색어”라고 한다. $n = 100$이라면 51번 이상 나타난 단어, $n = 501$이라면 251번 이상 출현한 단어가 인기 검색어이다. 어떤 경우에는 인기 검색어가 없는 경우도 있다. 예를 들어 인 단어 기록 {aa, ab, ac, aa, ad, ae}가 주어질 때, 이 경우에는 과반을 차지하는 단어가 없으므로 인기 검색어가 존재하지 않는다. 여러분은 주어진 단어 기록에서 인기 검색어를 찾아내는 프로그램을 작성해야 한다.

 

[입출력]

입력파일 words.inp의 첫줄에는 입력 단어의 수를 나타내는 이 주어진다. 이 수의 범위에 대한 제한은 $5 \leq n \leq 1000000$이다. 이어지는 N줄에는 소문자로 구성된 단어(word)가 한 줄에 하나씩 각각 주어진다. 여러분은 words.inp을 읽어 과반을 차지하고 있는 “인기 검색어”를 찾아 해당 단어를 출력해야한다. 만약 인기검색어가 없으면 대문자로 구성된 단어 ‘NONE’를 첫 줄에 출력해야 한다. 단어의 최대 길이는 256이다.

 

[예제]

words.inp	words.out		words.inp	words.out
11 protos dog computer protos protos dog dog protos algorithm protos protos	protos		11 protos dog computer protos protos dog dog zerg algorithm protos protos	NONE

[풀이]$O(N)$ 또는 $O(N\log_2N)$

먼저 $O(N\log_2N)$의 풀이.

가장 먼저 생각해낸 풀이다. 정렬해서, (index에 있는 단어기준으로 upper_bound로 다음 index를 찾아서, 현재 index와의 차가 과반이상이면 인기 검색어, 아니면 다음index로 넘어가기) 를 while loop돌리면 판별 가능하다.

최악의 경우는 모든 단어가 distinct할 때 upper_bound로 다음 index찾는 작업을 $n$번 돌리게 되므로 $n\log_2n$이다.

 

$O(N)$의 풀이.

boyer-moore voting algorithm

Boyer-Moore Voting Algorithm / 과반수 투표 알고리즘

kmp로 유명한 보이어무어 듀오의 과반수투표 알고리즘이다. 위 블로그에서 잘 못 된 설명을 내가 댓글로 지적했는데, 왜 그런지 생각해볼 수 있어서 위 블로그 링크로 담았다. 알고리즘 설명은 구글에 검색하면 많이 나오니 다른 블로그를 보도록 하자.

 

boyer-moore알고리즘으로 과반을 뽑는 경우, 뽑아낸 result가 진짜 과반이 넘는 result인지 판단이 불가능하다.

그 예로,1 1 2 3 4 4을 보자. cnt의 변화를 보면, 1 2 1 0 1 2가 되고, result는 4가 나올것이다. 진짜 4가 과반이 넘나?

아 그럼 cnt가 나온 횟수가 아닌가? 생각 할 수 있는데, 1 2 1만 봐도 아님을 알 수 있다.

따라서, 과반이 아님을 판별하려면 뽑아낸 result를 다시 for loop돌면서 다시 cnt를 세어주는 수 밖에 없다. 그래도 $O(N)$이니 전혀 부담되지 않는다.

 

[코드 $O(N)$]

[코드 $O(N\log_2N)$]