[Array/String] Majority Element

1. 문제

LeetCode - Majority Element

• 배열 nums에서 배열의 길이(n)의 절반 보다 많이 존재하는 요소인 majority element를 찾는 문제
• 문제에서는 majority element가 존재한다는 가정을 하고 풀어도 좋다고 하였다.

2. 접근법

• HashMap을 사용해 요소를 key로, 요소의 등장 빈도 수를 value로 사용할지 vs 별도의 배열을 선언하여 nums의 요소를 인덱스로 사용한 뒤에 해당 인덱스의 등장 빈도수를 업데이트 하는 방법을 사용할 지 고민
• nums의 요소를 인덱스로 사용하고, 가장 큰 빈도 수가 담긴 인덱스를 반환하는 방법으로 접근
• nums의 요소가 음수도 존재할 수 있다는 제약 조건으로 첫 접근 방법 실패
• 일단 naive한 접근 방법인 이중 반복문으로 접근하여 해결 -> 향후 HashMap 사용 버전으로 개선하여 Runtime 18ms로 단축

3. 풀이

class Solution {
    public int majorityElement(int[] nums) {
        /*
        배열 nums의 각 요소의 등장 빈도를 세어 maxCount 업데이트
        maxCount를 업데이트 하면서 해당 요소의 인덱스 갱신
        */

        // 1. 각 요소의 등장 빈도를 세어 줄 maxCount
        int maxCount = 0;

        // 2. maxCount가 업데이트 되는 지점의 인덱스를 담아 줄 idx
        int idx = 0;

        // 3. 이중 반복문을 통해 배열 nums를 순회하면서 maxCount 및 idx 업데이트
        for (int i = 0; i < nums.length; i++) {
            // 매번 업데이트 해야 하므로 count를 0으로 갱신
            int count = 0;

            for (int j = 0; j < nums.length; j++) {
                // 요소가 같으면 count 업데이트
                if (nums[i] == nums[j]) count++;
            }

            // maxCount 및 idx 갱신
            if (count > maxCount) {
                maxCount = count;
                idx = i;
            }
        }

        // maxCount가 업데이트 된 인덱스의 요소를 반환
        return nums[idx];
    }
}

4. 성능

- Runtime : 2854ms -> 18ms

- Memory : 48.5mb -> 47.1mb

5. 개선

• 처음에 생각했던 다른 방법인 key-value 자료 구조인 HashMap을 활용하는 방법
• 시간 복잡도를 이중 반복문의 O(n*n) -> O(n)으로 개선

class Solution {
    public int majorityElement(int[] nums) {
        // HashMap 사용 방법
        // nums의 요소를 key로, 등장 빈도를 value로 활용

        // 1. map 선언 및 초기화
        Map<Integer, Integer> map = new HashMap<>();

        // 2. nums를 순회하면서 map 업데이트
        for (int i = 0; i < nums.length; i++) {
            // 2-1. key가 존재하면 등장 빈도 갱신
            if (map.containsKey(nums[i])) {
                int count = map.get(nums[i]) + 1;
                map.put(nums[i], count);
            }

            // 2-2. key가 없으면 생성 및 value 1 할당
            else {
                map.put(nums[i], 1);
            }

            // 2-3. n / 2 보다 많이 등장하면 majority element이므로 반환
            if (map.get(nums[i]) > nums.length / 2) {
                return nums[i];
            }
        }

        return -1;
    }
}