[Leetcode] 169. Majority Element - C++

 

문제 링크

 

주어진 int 배열에서 가장 많이 등장한 숫자를 리턴하는 문제이다.

 

• 접근 방식
  1. 주어진 nums 배열을 한바퀴 돌면서 각 자리의 숫자와 해당 숫자의 등장 횟수를 센다.
  2. 현재 최대로 등장한 숫자를 저장한다.
• 구현 코드

#include <iostream>
#include <vector>
#include <unordered_map>

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int maxCntNum = -1;
        std::unordered_map<int, int> countMap;

        for (int item : nums) { 
            countMap[item]++;
        }
        
        for (const auto& maxCandidate : countMap) {
            if (countMap[maxCntNum] < maxCandidate.second) {
                maxCntNum = maxCandidate.first;
            }
        }
        return maxCntNum;
    }
};

 

- 시간 복잡도는 O(n) 이라서 무난하게 풀었다고 생각했는데 O(1) 방식도 있었다!

- 다른 사람의 풀이를 보면서 Boyer-moore 알고리즘에 대해 알게 되었다. 문자열 검색 알고리즘이라는데 아직 이해가 잘 안된다 🥹