169. Majority Element (C++)

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

Majority Element - LeetCode

 

한 배열 안에서 가장 많은 숫자가 무엇인지 알아내는 문제인데

문제의 조건에서 The majority element is the element that appears more than ⌊n / 2⌋ times. 

이라고 나와있다. 즉, 가장 많은 숫자 등장 횟수는 배열 길이의 절반 이상보다 많다는 걸 의미한다.

 

이게 Boyer-Moore Voting Algorithm이라고 한다. 역시 학부생 때 알고리즘 공부를 좀 소홀히 했더니 모르는게 많다. 이런 정렬 알고리이나 탐색 알고리즘은 현업에서도 꽤나 유용하게 쓰일 수 있기 때문에 이런 것도 많이 공부해야 겠다.

 

그래서 풀이는 아주 간단하다.

 

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