🟢[Leet code - 169] Majority Element ✅

Majority Element - LeetCode

 

문제

• Input
  정수 배열 nums
  
  
• Output
  nums.size의 절반을 초과하여 등장하는 원소 반환
  
  
• Constraints
  항상 많이 나타나는 원소가 무조건 존재함
  
  

 

시간 복잡도

※1초에 1억 번을 대략적인 기준으로 삼는다.

 

$1 \le n \le 50'000$으로 n의 최대 크기는 $50'000$이다.

$O(n \log n)$의 복잡도부터 고려해볼  수 있다.

 

 

해결 과정

한 번 순회하면서 각 원소의 등장 횟수를 카운트하는것이 가장 직관적이고 간단하다고 생각했다.

원소에 음수도 있기 때문에 값을 인덱스로 사용하는 정적배열은 사용하기 힘들어,
필요한 원소만 저장하는 겸 map을 사용하기로 했다.

또한 순회 도중 최대 값과 해당 값의 카운트를 저장하고 있어야했기 때문에, 한번에 저장할 겸 Iterator를 사용했다.

순회를 한 번하는 O(n)의 복잡도를 가지기 때문에 충분히 가능한 풀이라고 생각했다.

 

 

구현

int majorityElement(vector<int>& nums) 
{
    unordered_map<int,int> map;
    unordered_map<int,int>::iterator ret = map.insert({0,0}).first;

    for(int el : nums)
    {
        if (ret->second < ++map[el])
            ret = map.find(el);
    }

    return ret->first;
}

 

 

되돌아보기

• iterator의 사용법
  오랜만에 사용해서 방법을 까먹었어서, 복기할겸 정리한다.
  container<T>::iterator 로 정의하고, → 연산자를 사용하여 first는 key, second는 value에 접근한다.
  
  
• map.insert의 반환 값
  코드를 깔끔하게 하기 위해 inset의 반환 값이 있는지 찾아보고 사용했다.
  std::pair<iterator, bool> 형으로 반환하고, first는 삽입되거나,이미 존재한 iterator를, second는 성공 여부를 반환한다.
  
  
• Boyer-Moore Voting Algorithm
  해당 문제에서는 공간 복잡도를 O(1)로 풀어보라는 도발을 하였는데, 나는 무참히 패배했다.
  해당 알고리즘은 다른 글에 정리하였다.

Boyer-Moore Voting Algorithm

 

 

개선 코드

Boyer-Moore Voting Algorithm을 사용한 코드다.

int majorityElement(vector<int>& nums) 
{
	int candidate = 0;
	int count = 0;
    
	for (int num : nums) 
	{
		if (count == 0) candidate = num;
		count += (num == candidate) ? 1 : -1;
	}
	return candidate;
}