6) LeetCode - Majority Element

https://leetcode.com/problems/majority-element/?envType=study-plan-v2&envId=top-interview-150

---

처음 문제를 풀 때 단순히 배열에 넣어야겠다고 생각했지만 너무 많은 숫자를 다룰 수 있기에 다른 방법을 생각했다.

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> elements;
        int max = 0, max_num = 0;
        for(int& i : nums)
        {
            elements[i]++;
            if(max < elements[i])
            {
                max = elements[i];
                max_num = i;
            }
        }
        return max_num;
    }
};

unordered_map을 활용하면 삽입도 O(1), 탐색도 O(1)이기 때문에 시간적인 측면에서 큰 효율을 가져올 수 있다.

 

하지만 다른 방법을 생각해보면 for문을 제외하고 O(1)의 시간복잡도를 가지면서 O(1)의 공간복잡도도 챙겨올 수 있다.

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int max = 0, max_num = 0;
        for(int& i : nums)
        {
            if(max == 0)
            {
                max_num = i;
                max++;
            }
            else
            {
                if(max_num != i)
                {
                    max--;
                }
                else
                {
                    max++;
                }
            }
        }
        return max_num;
    }
};

nums 배열에서 가장 많이 나오는 숫자를 묻는 문제지만 얼마나 많이 나왔는지는 중요하지 않다.

따라서 변수 하나를 사용하여 공간에서 이득을 볼 수 있다.

i 번째 배열까지 체크했을 때 max_num의 숫자가 많다면 max는 0이거나 0이 되지 않을 것이다.

i 번째 배열까지 체크했을 때 max 가 0이 된다면 지금까지 숫자 중 가장 많은 숫자의 종류는 2가지 이상이 될 것이다.

하지만 이후로도 더 많이 나오는 숫자는 max가 0이 된 순간 다시 얻을 수 있을 것이다.

 

 

LeetCode FollowUp 쉽지 않다...