[leetCode] 169. Majority Element (Easy) 풀이

❓ 문제

Given an array nums of size n, return the majority element.

크기가 n인 배열 개수가 주어지면 가장 많은 요소를 반환하세요.

 

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

가장 많은 요소는 ⌊n / 2⌋번 이상 나타나는 요소입니다. 가장 많은 요소가 항상 배열에 존재한다고 가정할 수 있습니다.

Example 1:

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

Example 2:

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

❗ 내 답변

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    let obj = {};
    nums.forEach(num => {
        if (! obj[num])
            obj[num] = 1;
        else
            obj[num]++;
    })
    const maxCnt = Math.max(...Object.values(obj));

    for (let num in obj) {
        if (obj[num] === maxCnt)
            return num;
    }
};

이전에 풀었던 Single Number 문제와 비슷하게 풀었다.

 

obj 에 요소와 요소의 개수를 각각 키, 값으로 담고,
개수 값이 최대인 것을 반환시켰다.

 

예를 들어 [2,2,1,1,1,2,2] 가 nums 로 들어온다면,
obj 는 아래와 같이 될 것이다.

{
    '2': 4,
    '1': 3
}

개수 값이 4로 가장 큰 2가 반환되게 된다.

 

여담으로..
요즘 leetCode 가 잘 안풀어져서 JavaScript 알고리즘 강의를 구매해서 수강중인데,
빅오 표기법에 대해 배우고 있다.

 

내가 푼 알고리즘을 빅오 표기법으로 표현한다면,
시간복잡도와 공간 복잡도 모두 O(n) 이 되겠다.

 

nums 의 크기만큼 늘어날 수 있는 obj을 할당하고 있고,
nums 의 크기만큼 반복을 도는 로직이 있기 때문이다.

반복이 여러개 있지만 모두 O(n)이기 때문에, O(n)이 된다.
(가장 시간복잡도가 큰 것이 현 시간복잡도로 표기됨)

❗ Runtime이 가장 빨랐던 답변과 비교

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {

    let count =1;
    let major= nums[0];
    const len=nums.length;
    for( let i=1;i<len;i++){
        if(count===0){
            count ++;
            major=nums[i];
        }
       else if(nums[i]===major){
           count ++;
       }else {
           count --;
       }
    }
    return major;
};

반복을 돌면서 count를 증감시키고 있다.
초기엔 major 에 첫번째 요소를 담아두었다가,
반복을 돌면서 count가 0이라면 major를 현재 값으로 변경하고 count 를 증가 시킨다.

이게 무슨 뜻인고...아래 예를 보며 알아가자.

예를 들어 [2,2,1,1,1,2,2] 가 nums 로 들어온다면,

초기엔 major 가 nums[0]으로 2가 될것이고
count 는 1이다.

 

아래는 반복 과정이다.

i	nums[i]	count	major
1	2	2	2
2	1	1	2
3	1	0	2
4	1	1	1
5	2	0	1
6	2	1	2

마지막 major 값인 2를 반환하게 된다!

 

같은 값을 마주하면 카운트가 올라가지만,
다른 값을 마주하면 카운트가 깎이게 된다.
깎이고 깎이다가 0이되면 major를 다시 셋하고 count도 초기화 시킨다.
즉, 이전에 마주했던 값들 보다 동일한 게 더 많이 존재하는 값이 나타났으니 리셋시키는 거다.

 

사실 난 이 솔루션을 완벽하게 이해 못했었다
처음엔 [2,2,1,1,1,3,3] 이 nums 로 들어오면?? [4,4,4,4,4,4,1,2,3,5,6,7,8] 이 들어오면 다른 답이 나오는데?!
라고 생각했었는데, 문제를 제대로 안 읽어 든 생각이었다 ㅎㅎ...

가장 많은 숫자가 항상 nums.length/2보다 크다고 했으니
[2,2,1,1,1,3,3] 에서 1이 가장 많은 수가 되려면 1이 한번 더 있어야하고,
[4,4,4,4,4,4,1,2,3,5,6,7,8] 에서 4가 가장 많은 수가 되려면 4가 한번 더 있어야한다.

 

그리고 왜 1부터 시작하는거지?? 하나는 왜빠뜨리고 반복 도는 거지?!
라고 생각했었는데,
비교를 위해 가장 첫번째 값을 major 로 두고 진행했기 때문이었다...ㅎㅎ
머리가 안돌아가는구만...

 

이 답변은 공간 복잡도가 O(1), 시간 복잡도가 O(n)이다.
개인적으론 다소 이해하기 힘들었지만 성능이 가장 좋은 답변 같다.

❗ Memory 사용이 가장 적었던 답변과 비교

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    let maxCount = nums.length/2, count = 0
    for(let i = 0; i<nums.length; i++){
        count = 0
        for(let j = 0; j<nums.length; j++){
            if(nums[i] === nums[j]) count++
        }
        if(count > maxCount) return nums[i]
    }
};

중첩반복문을 사용했다!

메모리 사용은 적을지 몰라도(O(1)) 시간 복잡도는 O(n^2) 가 된다.

maxCount 를 nums.length/2로 둔다.
서로 같은 값이 있으면 증가키고, 증가된 값이 maxCount 보다 크면 냅다 반환한다.
(왜냐면, 가장 값이 많은 요소는 항상 nums.length/2 보다 크다는 조건이 있었기 때문에!)

개인적으로 Runtime이 가장 빨랐던 답변보다 가독성이 좋고 이해하기 쉬웠다.

💡 개선 방안

반복과 메모리 할당을 줄여보자!