Majority Element

problem

주어진 배열에서 가장 대중적인 값을 찾는 문제입니다.
https://leetcode.com/problems/majority-element/

solution

풀이1

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        map<int,int> m;
        for(int i=0;i<nums.size()/2;i++){
            m[nums[i]] += 1;
        }
        for(int i=nums.size()/2;i<nums.size();i++){
            m[nums[i]] += 1;
            if(m[nums[i]] > nums.size()/2){
                return nums[i];
            }
        }
        return -1;
    }
};

풀이2

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int major = nums[0], count = 1;
        for(int i=1;i<nums.size();i++){
            if(major == nums[i]){ count++;}
            else{
                count--;
                if(count == 0){ major = nums[i]; count++;} 
            }
            
        }
        return major;
    }
};

후기

이런 생각은 어떻게 하면 할 수 있는거지
한번 보고 나면 이해되고 이생각을 왜 못했지? 이러는데
막상 처음에 생각하려고 보면 너무 어려운 것 같습니다.

배열의 크기 = n 이라하면 가장 대중적인 문자는
어차피 n/2 이상 같은 문자가 나오므로
count --로 다른 문자들을 다 0으로 만들어버립니다.

엄청 깔끔하고 효율적인 생각인 것 같습니다.