[LeetCode] Majority Element - Javascript

Majority Element

[과반수 요소 찾기]

제약 조건 

n == nums.length
1 <= n <= 5 * 10^4
-10^9 <= nums[i] <= 10^9

 

Example

ex1) Input: nums = [3,2,3]
     Output: 3

ex2) Input: nums = [2,2,1,1,1,2,2]
     Output: 2

초기 문제 접근 방식

obj 빈 객체를 생성하고 객체 key는 배열의 "값"으로 객체의 value는 "값의 개수"를 넣는다.
예시로 들면 아래와 같다.

nums = [2,2,1,1,1,2,2]

obj = {2:4,1:3}

 

그 후 객체의 key를 이용해 값의 max 값을 찾고
해당 max 값을 이용해 정답을 도출할 수 있었다.

 

문제를 풀고 다른 풀이법을 보면서 느꼈지만,
초기 문제를 풀 때는 과반수의 개념을 잘 이해하지 못한 채로 접근했다.

초기 전체코드

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function (nums) {
   const Obj = {};
   for (let i = 0; i < nums.length; i++) {
      if (Obj.hasOwnProperty(nums[i])) {
         Obj[nums[i]]++;
      } else {
         Obj[nums[i]] = 1;
      }
   }

   const arr = Object.keys(Obj);
   let answer = 0;
   let max = 0;
   for (let i = 0; i < arr.length; i++) {
      if (max < Obj[arr[i]]) {
         max = Obj[arr[i]];
         answer = arr[i];
      }
   }
   return answer;
};

위의 코드로 문제는 풀 수 있었다.
하지만 코드를 작성하면서도 답을 도출해 낼 수 있지만, 효율적인 방법이 아닐 거란 건 직감적으로 느꼈다.

 

다시 생각 해보며.. , 다른 sovle 코드

아래의 풀이법을 보고 과반수의 의미에 대해 알 수 있었다.
우선 과반수의 배열이 넘어오는 온다는 건, 같은 개수의 값이 넘어올 일이 없다는 것이다.

ex) 1,1,2,3 -> O

ex) 1,1,2,2,3 -> X

 

제일 먼저 nums 배열을 정렬을 하고 nums 배열의 길이에 나누기 2를 한 후 내림 연산을 수행한다.
연산이 된 결괏값은 반드시 과반수의 값이 된다.

var majorityElement = function(nums) {
    nums.sort((a, b) => a - b);
    return nums[Math.floor(nums.length / 2)];
};

배열의 중간값은 무조건 과반수의 값이 될 수밖에 없다는 점을 이용한 풀이 방법이다.