[알고리즘] LeetCode Majority Element JS

개요

주어진 배열에서 가장 많이 나온 원소를 찾아 리턴하는 문제이다.

Majority Element - LeetCode

 

풀이

해쉬맵으로 쉽게 구현할 수 있었다.

처음엔 주어진 배열로 해쉬맵을 만들고 만들어진 해쉬맵에 키값으로 한번 더 돌려 구현하였다.

거기서 가장 큰 원소의 값을 answer 변수에 넣어 리턴하는 간단한 문제이다

/**
 * @param {number[]} nums
 * @return {number}
 *
 * 가장 많이 나온 원소의 갯수를 찾는 문제이다.
 */
var majorityElement = function (nums) {
  const map = new Map();

  for (const char of nums) map.set(char, (map.get(char) || 0) + 1);

  let answer = nums[0];

  for (const key of map.keys())
    if (map.get(key) > map.get(answer)) answer = key;

  return answer;
};

 

Discuss

Boyer-Moore Voting

과반수 알고리즘이라고도 불리는데 아주 단순하다.

과반수만 넘는다는게 보장된다면 정답은 항상 과반수 원소라는 것이다.

 

쉽게 원소 100개가 있을 때 51개가 A원소라면 남은 모든 원소의 갯수만큼 다 빼더라도 정답은 A가 된다.

아래 코드가 그렇게 구현되어있고 선형탐색으로만 정답을 도출할 수 있었다

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

var majorityElement = function(nums) {
    
    // Boyer-Moore Voting Algorithm
    
    let count = 0, candidate = 0
    
    for (let num of nums) {
        if (count == 0) {
            candidate = num
        }
        count += num == candidate ? 1 : -1
    }
    
    return candidate
};