[LeetCode] 169. Majority Element - Java

 

Majority Element - LeetCode

 

문제

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

 

Example 1:

Input: nums = [3,2,3]
Output: 3

Example 2:

Input: nums = [2,2,1,1,1,2,2]
Output: 2

 

Constraints:

• n == nums.length
• 1 <= n <= 5 * 104
• -109 <= nums[i] <= 109

 

Follow-up: Could you solve the problem in linear time and in O(1) space?

 

길이가 n인 주어진 배열 nums에서 가장 많은 요소를 반환하는 문제이다.

가장 많은 요소는 n/2 이상 나타난 요소이다.

 

---

 

내 풀이

import java.util.*;
class Solution {
    public int majorityElement(int[] nums) {
        int answer = 0;
        Map<Integer, Integer> map = new HashMap<>();

        for(int i=0; i<nums.length; i++){
            map.put(nums[i], map.getOrDefault(nums[i], 0)+1);
        }

        int n = nums.length / 2;
        for(Map.Entry<Integer, Integer> entrySet : map.entrySet()){
            if(entrySet.getValue() > n){
                answer = entrySet.getKey();
            }
        }

        return answer;
    }
}

일단 제일 먼저 떠오른 생각은 HashMap을 사용하는 풀이이다.

HashMap각 요소들의 개수를 저장한 후 맵을 순회하면서 가장 많은 개수를 가지는 값을 찾았다.

• 시간복잡도 : O(n) + O(n) ≈ O(n)
• 공간복잡도 : O(n)

 

---

 

다른 사람의 풀이

이 문제 역시 공간복잡도를 O(1)로 유지하면서 풀이가 가능할 것 같아 다른 사람의 풀이를 찾아보았다.

class Solution {
    public int majorityElement(int[] nums) {
        int answer = 0;
        int count = 0;

        for(int i=0; i<nums.length; i++){            
            if(count == 0){
                answer = nums[i];
            }

            if(answer == nums[i]){
                count++;
            }else{
                count--;
            }
        }
        return answer;
    }
}

문제에서 가장 많은 요소는 n/2 이상 나타난 요소, 즉 과반수를 차지하는 요소라고 주어졌다.

주어진 정수 배열에서 과반수를 차지하는 요소를 공간 복잡도 O(1)로 찾는 ‘보이어-무어 과반수 투표 알고리즘’ 이라고 불리는 방법이다.

 

저장된 요소가 적어도 반 이상의 요소를 차지하고 있을 때, 다른 요소를 만날때마다 count를 줄이는 방식으로 동작한다.

count가 0이되면 저장된 요소를 바꾼는 방식으로 문제를 해결한다.

 

과반수 이상을 차지하는 요소를 찾으면 되니까 내 풀이처럼 모든 요소의 개수들을 저장할 필요가 없었다.

이제까지는 공간복잡도에 대해 크게 생각하지 않고 알고리즘 문제들을 풀어왔었는데, 내가 푼 풀이의 복잡도를 항상 계산해보고 최선의 풀이를 찾아야겠다는 생각을 했다.