LeetCode 169. Majority Element

169. Majority Element

문제

크기가 n인 배열 nums의 majority element를 리턴하시오.

majority element는 배열에서 n / 2 번 이상 포함된 요소를 의미합니다. (과반 요소)

항상 majority element가 있다고 가정해도 좋습니다.

의사코드 또는 풀이 계획

1. 배열의 요소 별로 몇 개의 요소가 있는지 map에 저장
2. 배열의 요소를 키로 설정하고 요소별 개수를 값으로 설정
3. 배열을 한 번 더 순회하면서 개수가 가장 큰 값을 값으로 리턴
4. 문제의 조건에는 n / 2번 이상 포함된 요소라고 했지만 샘플 답변을 보았을 때 해당 배열에서 가장 많이 존재하는 요소라고 가정해도 좋을 듯.

풀이

class Solution {
    public int majorityElement(int[] nums) {
        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 key = 0;
        int maxCnt = 0;
        for (int el : nums) {
            if (map.get(el) > maxCnt) {
                maxCnt = map.get(el);
                key = el;
            }
        }
        
        return key;
    }
}

아래의 2번 풀이에서 map.entrySet()을 이용해서 풀기 가능

다른 풀이

1. sorting

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        return nums[n/2];
    }
}

배열을 정렬한 후 중간 요소를 찾는다. 과반 요소(majority element)는 항상 배열의 중간 인덱스를 차지한다.

[2, 2, 1, 1, 2]
[1, 1, 2, 2, 2]
int n = nums.length // 5
return nums[5/2] // nums[2] : 2

2. HashMap (나의 접근과 같지만 key값 구하는 코드가 조금 더 세련되다.)

class Solution {
    public int majorityElement(int[] nums) {
        int n = nums.length;
        Map<Integer, Integer> map = new HashMap<>();
        
        for (int i = 0; i < n; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        
        n = n / 2;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() > n) {
                return entry.getKey();
            }
        }
        
        return 0;
    }
}

n 변수에 nums의 과반을 구한다.
map.entrySet()을 이용하여, entry.getValue()을 한 후 과반의 값인 n보다 클 경우 entry.getKey()를 이용해 그 키를 구한다.

3. Moore Voting Algorithm

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;
    }
}

1. 이 알고리즘은 배열의 첫 번째 요소를 과반 후보로 가정하고 알고리즘을 시작합니다.
2. 과반 후보로 설정 후 count를 1로 올립니다.
3. 다음 후보가 이전에 설정된 후보와 같다면 count를 증가시킵니다.
4. 같지 않다면 count를 내립니다.
5. count가 0이 된다면 다음 순회할 요소를 다음 후보로 설정합니다.
6. 배열의 순회가 끝나고 candidate로 설정되어 있는 요소를 리턴합니다.