[Leetcode/C++] 169_Majority Element

문제는 다음과 같습니다.

쉽지만, 새로운 알고리즘을 배울 수 있었던 문제였습니다.
➡️ 가장 마지막 풀이에 소개하겠습니다.
총 3가지 방법으로 풀었는데, 다음과 같습니다.

1. hash 이용

key에 해당 숫자와, value에 해당 숫자가 나온 횟수를 계산하여,
hash map의 value중 최댓값을 구해주면 됩니다.
전체 코드는 다음과 같습니다.

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> um;
        for(int i=0; i<nums.size(); i++) um[nums[i]]++;
        int key=0, val=0;
        for(auto a: um){
            if(a.second>val){ key=a.first; val=a.second; }
        }
        return key;
    }
};

2. sort

문제를 잘 읽어보면, 가장 많이 나온 수는 전체 수의 절반이상으로 나온다고 합니다.
(The majority element is the element that appears more than ⌊n / 2⌋ times.)
따라서 정렬을 수행한 뒤, 벡터의 절반에 위치한 원소는 항상 전체 벡터 원소 중 가장 많은 빈도수의 원소입니다.

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        return nums[nums.size()/2];
    }
};

3. Boyer-Moore algorithm(보이어 무어 알고리즘)

이 풀이는 discussion에서 가장 많은 투표수를 얻은 풀이를 제가 조금 제 방식으로 다듬은 풀이입니다.
해당 풀이에서 사용한 알고리즘은 Boyer Moore 알고리즘으로, 주로 문자열 검색 알고리즘에서 쓰인다고 합니다.

문자열 문제를 풀때, 이 알고리즘과 KMP는 꼭 정리해두도록 하겠습니다.😊

✏️원리는 다음과 같습니다.✏️
임의로 첫 원소를 val에 저장하고, cnt는 카운트를 해주는 변수입니다. 처음엔 1로 시작합니다.
이후, 벡터의 두번째원소부터 끝까지 돌면서,

• val과 같은 원소라면 -> cnt++;
• val과 다른 원소라면 -> cnt--;

이때, for문의 가장 위에 오는 if문은 다음과 같습니다.

if(cnt==0) val=nums[i];

cnt==0 이라는 것은, 기존의 가장 많이 나왔던 원소와 같은 빈도수의 원소가 있다는 것입니다.
이 경우에는 val의 값을 현재 원소로 대체하면 됩니다.

이 원리로 끝까지 원소를 검사하면 됩니다.

전체 코드는 다음과 같습니다.

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