[leetcode] 169. Majority Element

문제

 

배열에서 특정 요소가 과반수 이상 등장하는 경우 그 요소를 찾는 문제입니다. 과반수 요소는 배열의 길이 n의 절반 이상 등장하는 요소로 정의됩니다.

 

주어진 배열 nums에서 과반수 요소를 찾는 문제입니다. 과반수 요소는 항상 존재한다고 가정합니다.

 

 

풀이

해당 문제는 Hash Map를 이용해서 풀 수 있습니다. 하지만 이 문제의 추가 조건으로 로 “문제를 O(n) 시간 복잡도와 O(1) 공간 복잡도로 해결할 수 있는지”가 주어졌습니다. Hash Map를 이용하면 공간복잡도가 O(n)으로 해당 조건을 만족할 수 없습니다.

 

해당 조건에 맞춰 문제를 해결하려면  Boyer–Moore majority vote algorithm를 이용하여 풀 수 있습니다.

Boyer–Moore majority vote algorithm은 과반수 요소를 찾기 위한 효율적인 알고리즘입니다. 이 알고리즘은 O(n) 시간 복잡도와 O(1) 공간 복잡도로 문제를 해결할 수 있어, 추가 메모리 없이도 과반수 요소를 찾아낼 수 있습니다.

 

 

코드

1. Hash Map을 이용한 풀이

HashMap을 사용하여 각 요소의 빈도를 기록하고, 과반수 이상 등장한 요소를 찾습니다.

class Solution {  
    public int majorityElement(int[] nums) {  
        Map<Integer, Integer> frequencyMap = new HashMap<>();  
        int result = 0;  
        int maxCount = 0;  
  
        for (int num : nums) {  
            int count = frequencyMap.getOrDefault(num, 0) + 1;  
            frequencyMap.put(num, count);  
  
            if (count > maxCount) {  
                result = num;  
                maxCount = count;  
            }  
        }  
        return result;  
    }  
}

 

설명

1. frequencyMap에 각 요소의 빈도를 저장

2. 요소 num의 빈도가 maxCount보다 크다면, result를 num으로 업데이트하고 maxCount를 현재 빈도로 갱신

3. 배열 순회가 끝나면 result에 과반수 요소가 저장되어 반환

 

시간 및 공간 복잡도

• 시간 복잡도: O(n), 배열을 한 번 순회하면서 각 요소의 빈도를 기록합니다.

• 공간 복잡도: O(n), HashMap을 사용하여 각 요소의 빈도를 저장하기 때문에 공간 복잡도는 O(n)입니다.

 

 

2. Boyer–Moore majority vote algorithm

Boyer–Moore majority vote algorithm을 사용하면 O(n) 시간 복잡도와 O(1) 공간 복잡도로 문제를 해결할 수 있습니다. 

 

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

 

설명

 

1. count 변수를 사용하여 현재 result의 “과반수 여부”을 관리

2. count가 0이면 새로운 후보로 num을 설정

3. num이 현재 후보(result)와 같으면 count를 증가시키고, 다르면 count를 감소시킴

4. 최종적으로 result에 과반수 요소가 저장되어 반환

 

시간 및 공간 복잡도

• 시간 복잡도: O(n), 배열을 한 번만 순회합니다.

• 공간 복잡도: O(1), 추가적인 공간을 사용하지 않습니다.