Daily Leetcoding Challenge 229. Majority Element II

https://leetcode.com/problems/majority-element-ii

LeetCode - The World's Leading Online Programming Learning Platform

직관

배열의 원소가 출현한 횟수를 Map에 저장해서 활용하는 문제를 여러 번 다뤄봤기 때문인지 바로 떠오른 방법은 원소를 키로 하고 출현 횟수를 값으로 하는 Map을 사용하는 것이다. 이 경우 Map에 최대 n개의 값이 저장될 수 있다. Follow up에서 공간 복잡도를 O(1)로 풀 수 있는지 물어봤기 때문에 더 효율적인 알고리즘이 있을 것 같았다.

Boyer-Moore Majority vote 알고리즘이 바로 그것이다. 원래의 알고리즘은 과반의 투표 후보(1/2 넘게)가 있는지 찾는 알고리즘이다. 그래서 count, candidate 변수 두 개가 필요하지만 여기서는 1/3 넘게 출현한 원소를 찾고 있다. 1/3 넘게 출현하는 원소는 많아야 2개 존재하기 때문에 count1, count2, candidate1, candidate2 변수 2개를 추가로 더 선언하여 구현한다.

접근법

1. count1, count2, candidate1, candidate2를 0으로 초기화한다.

2. nums의 각 원소 n에 대해서

  2-1. n == candidate1 이면 count1을 +1 한다.

  2-2. n == candidate2 이면 count2를 +1 한다.

  2-3. count1 == 0이면 candidate1 = n, count1 = 1로 갱신한다.

  2-4. count2 == 0이면 candidate2 = n, count2 = 1로 갱신한다.

  2-5. 위 경우에 해당하지 않는다면 count1, count2를 1씩 감소시킨다.

3. count1, count2를 0으로 초기화한다.

4. nums의 각 원소 n에 대해서

  4-1. n == candidate1 이면 count1을 +1 한다.

  4-2.n == candidate2 이면 count2을 +1 한다.

5. count1 > nums.length/3 이면 candidate1을 정답에 추가한다.

6. count2 > nums.length/3 이면 candidate2를 정답에 추가한다.

복잡도

Map을 활용하는 경우 nums의 원소를 최대 n개 저장할 수 있기 때문에 공간 복잡도가 O(n)이고, 시간 복잡도도 O(n)이다.

Boyer-Moore 알고리즘의 경우 후보 원소 2개만 저장하기 때문에 공간 복잡도는 O(1)이고, 시간 복잡도는 O(n)이다.

코드

Map을 활용한 구현 방법

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        int limit = nums.length/3;
        List<Integer> ret = new ArrayList<>();
        Map<Integer, Integer> freqMap = new HashMap<>();
        for(int n : nums) {
            int freq = freqMap.getOrDefault(n, 0);
            freqMap.put(n, freq+1);
        }
        for(Map.Entry<Integer, Integer> e : freqMap.entrySet()) {
            if (e.getValue() > limit) {
                ret.add(e.getKey());
            }
        }
        return ret;
    }
}

Boyer-Moore Majority Vote 알고리즘 응용한 구현

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        int candi1 = 0, candi2 = 0, count1 = 0, count2 = 0;
        for(int n : nums) {
            if (n == candi1) {
                count1++;
            } else if (n == candi2) {
                count2++;
            } else if (count1 == 0) {
                candi1 = n;
                count1 = 1;
            } else if (count2 == 0) {
                candi2 = n;
                count2 = 1;
            } else {
                count1--;
                count2--;
            }
        }
        List<Integer> ret = new ArrayList<>();
        count1 = count2 = 0;
        for(int n : nums) {
            if (n == candi1) {
                count1++;
            } else if (n == candi2) {
                count2++;
            }
        }
        if (count1 > nums.length/3) {
            ret.add(candi1);
        }
        if (count2 > nums.length/3) {
            ret.add(candi2);
        }

        return ret;
    }
}