다수 원소

지침

봉지에 든 사탕 중에서 봉지의 절반 이상을 차지하는 색이 있는지 알아내야 해요. 🍬 다수 원소는 컬렉션에서 절반이 넘는 자리를 차지하는 원소예요. 색을 나타내는 원소 목록이 주어지면, 다수인 색을 반환하고, 그렇지 않으면 다수 원소가 없다고 알려줘요.

간단한 목록 [Red, Red, Blue, Red, Green]에서는 5개 중 Red가 3번 등장하므로 반환값은 Red여야 해요. 하지만 [Red, Red, Blue, Green] 목록에서는 Red가 가장 흔한 원소임에도 2/4가 절반보다 크지 않기 때문에 다수 원소가 없어요.

구현

• 보너스 점수: 구현을 일반화해서 모든 타입의 List에서 다수 원소를 찾을 수 있나요?
• 보너스 점수: 다수 원소를 찾을 때 고를 수 있는 서로 다른 원소가 많아도 구현의 성능이 좋은가요?
• majorityFinder 함수는 원하는 방식으로 얼마든지 구현할 수 있지만, MyStore ability를 사용하는 몇 가지 스텁도 함께 준비해 두었어요. (MyStore ability는 표준 라이브러리의 Store와 같지만, 여기서는 이름이 겹치지 않도록 조금 다른 이름을 붙였어요.) 이 ability를 사용하기로 했다면 runWith 핸들러를 구현해야 해요. runWith는 MyStore ability를 사용하는 함수를 실행한 결과와 MyStore의 최종 상태를 모두 반환해요.
• ability 핸들러가 상태를 추적하는 방법에 대해서는 ability 핸들러 문서에서 더 읽어볼 수 있어요.

---

출처

Boyer Moore Majority Vote Algorithm