[Algorythm][JS] 과반수 찾기

문제

숫자로 이루어진 배열인 nums를 인자로 전달합니다. 숫자중에서 과반수(majority, more than a half)가 넘은 숫자를 반환해주세요.

예를 들어,

nums = [3,2,3]
return 3
​
nums = [2,2,1,1,1,2,2]
return 2
nums = [3,2,3]
return 3

nums = [2,2,1,1,1,2,2]
return 2
가정
nums 배열의 길이는 무조건 2개 이상

풀이

풀이는 2가지를 생각했다.
하나는 보이어 무어의 과반수 투표 알고리즘을 이용한 풀이,
하나는 아래의 map객체를 이용한 풀이이다.
기존의 정해진 알고리즘이 아닌 스스로 생각해낸 풀이를 먼저 작성해보기로 했다.

function moreThanHalf(nums) {
  let map = new Map();
  
  for(let i = 0; i < nums.length; i++) {
    const curr = nums[i];
    if(map.has(curr)) {
      const count = map.get(curr);
      map.set(curr, count + 1);
    } else {
      map.set(curr, 1);
      
    }
  }
  const answer = [...map].reduce((a, b) => {
    return a[1] > b[1] ? a : b;
  })[0];

return answer;
}

과반수 투표 알고리즘으로도 한번 풀어봐야겠다.