[C++] [LeetCode 169] Majority Element

 

---

문제 풀기 전 생각 : 

/*
먼저 입력받은 백터를 정렬한다.
그 후 저장된 숫자를 하나하나 전 숫자와 비교하며 
카운트를 한다.
마지막에 가장 많은 카운트를 기록한 숫자를 출력한다.
*/

---

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int max=0,max_i=0;
        int pre=0,pre_i=0;
        sort(nums.begin(),nums.end());
        for(int i=0 ; i<nums.size() ; i++){
            if(nums[i] != pre_i){
                if(pre > max){
                    max = pre;
                    max_i = pre_i;
                }
                pre_i = nums[i];
                pre = 1;
            }
            else {
                pre++;
            }
        }
        if(pre > max) max_i = pre_i;
        
        return max_i;
    }
};

https://leetcode.com/problems/majority-element/

Majority Element - LeetCode

---

풀 때 어려웠던 점 또는 느낀점 :

 

뭔가 너무 투박하게 푼 듯해서 

다른 사람의 풀이가 궁금하다.

---

개선방안 :

int majorityElement(vector<int>& nums) {
        int max_count = 1;
        int count = 1;
        int max_val = nums[0];
        
        for(int i = 1; i<nums.size(); i++)
        {
            if(nums[i] == max_val)
            {
                count++;
                max_count++;
            }
            else
            {
                count--;
                if(count < 0)
                {
                    max_count++;
                    max_val = nums[i];
                    count = 1;
                }
            }
        }
        
        return max_val;
    }

가장 등장한 빈도수가 높은 숫자는 최소 2/n회 등장한다는

가정으로 푼 문제인듯 하다 나의 코드보다 4ms 정도 빠르긴 한데

이렇게 풀고 싶진 않다 ㅋㅋㅋㅋㅋㅋ

신박하다