[LeetCode] 169. Majority Element

Majority Element - LeetCode

 

크기가 n인 int배열 이 주어지면 majority element를 반환합니다.
majority element는 ⌊n / 2⌋ 이상 나타나는 요소입니다.

majority element가 항상 배열에 존재한다고 가정할 수 있습니다.

 

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

히든 문제 O(1)의 공간만 사용해서 풀 수 있어?

 

먼저 단순히 생각하고 풀어보았습니다.

O(1)의 공간만 사용해서 풀 방법은 아직 떠오르지 않기 때문에

문제를 푸는도중이나 해결하고나서 도전해 보겠습니다.

 

문제접근

절반 이상을 차지하는 것을 찾아라??

곧 가장 많이 나타난 요소를 찾으라는 뜻입니다.

 

숫자를 카운트할때 자주 사용하는 HashMap을 사용해야겠다고 생각했습니다.

key : nums의 데이터

value : nums의 데이터가 등장하는 횟수

 

그리고 Max를 정하고 가장 많이 등장하는 데이터에 따라 값을 갱신해가는 방식으로 문제를 해결해보았습니다.

    public int majorityElement(int[] nums) {
        int limit = nums.length / 2;
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (var i : nums) {
            hashMap.put(i, hashMap.getOrDefault(i, 0) + 1);
        }

        int ret = 0;
        int max = 0;
        for (Integer key : hashMap.keySet()) {
            if (hashMap.get(key) > max) {
                max = hashMap.get(key);
                ret = key;
            }
        }

        return ret;
    }

 

 

그다지 효율적이지는 않습니다.

 

그 이유는 무엇일까요? 

HashMap을 사용해서 접근이 빠르게 될거라고 생각될 수 있지만

자바에서 HashMap은 기본사이즈가 16입니다.

그럼 16을 초과하게되면? 내부 알고리즘에따라 다르겠지만 보통 16*2를 하여 32사이즈의 공간을 만들고 복사를 하는

resize() 과정이 들어갑니다.

 

위 과정때문에 데이터가 많이들어온다면 여러번 resize를 하게되고 시간복잡도가 늘어나는 것으로 판단됩니다.

 

시간복잡도

nums에 for문 사용해 한번 탐색하고

HashMap에 원소를 탐색하고 한번씩 탐색하고 있습니다.  

 

HashMap이 resize가 일어나지 않는다면 O(n)입니다.

 

만약 for문을 돌면서 hashMap에 데이터를 넣은때 HashMap이 resize가 발생한다면

정확한 시간복잡도는 입력값에 따라 다르므로 측정하기 어렵지만

좋지 못할것입니다.

 

 

 다른 사람의 풀이

loop를 돌면서 count를 증감하고 있습니다.

그리고 count가 0이라면 candidate를 num으로 바꿔넣고 있습니다.

 

이 로직은 majority element가 항상 배열에 존재하기때문에 가능합니다.

따라서 최종 남은 candidate는 majority element가 되는것입니다.

 

class Solution {
   public int majorityElement(int[] nums) {
        int count = 0;
        int candidate = 0;
        
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            
            if (num == candidate) {
                count++;
            } else {
                count--;
            }
        }
        
        return candidate;
    }
}

 

시간복잡도

nums에 for문 사용해 한번 탐색하면서 모든 로직을 끝냈습니다.

O(n)의 시간복잡도가 필요합니다.

 

 

느낀점

HashMap을 사용할때 resize가 된다는 것을 주의해야하고

문제를 정확히 파악하면 더 좋은 풀이법을 생각해낼 수 있다는것을 알았습니다.

 

참고

Majority Element - LeetCode