[ LeetCode | Java ] 169. Majority Element

dokim·2023년 8월 25일

[LeetCode] Top 150 leetcode

[LeetCode] Top Interview 150

목록 보기

8/51

🏷️169. Majority Element

1. 문제 설명

주어진 크기 n의 배열 nums가 있을 때, 과반수 요소를 반환합니다.
과반수 요소는 ⌊n / 2⌋보다 더 많이 나타나는 요소입니다. 과반수 요소는 항상 배열에 존재한다고 가정할 수 있습니다.

Example 1:

Input: nums = [3,2,3]
Output: 3

Example 2:

Input: nums = [2,2,1,1,1,2,2]
Output: 2

Constraints:

n == nums.length
1 <= n <= 5 * 10^4
10^9 <= nums[i] <= 10^9

2. 접근 방식

가장 빈도가 높은 요소를 반환해야 합니다.

처음에는 정수의 경우 수만큼 길이의 새로운 배열을 만들어 nums[i] 정수를 index값으로 사용하여 카운트하려고 하였으나 nums[i]의 범위가 integer 범위만큼 너무 크기 때문에 다른 방법을 생각해 보았습니다.
Map 컬렉션인 HashMap을 사용하여 Key에는 nums[i]를, Value에는 빈도수를 저장합니다. 저장하면서 Value > n/2 인지를 확이하여 맞다면 최빈값으로 반환합니다.

3. 의사 코드


	HashMap<Integert, Integer> map;
    
    for (num : nums){
    	map.put(num, ?) 데이터가 없으면 초기값 설정, 있으면 1씩 증가
        if( map.get(num) > nums길이/2 )
        	num 반환
    }

4. 구현 코드

Map의 getOrDefault(Key, Default-Value) +1을 사용하여 데이터가 없으면 0으로 초기화 하고, 데이터가 있으면 +1을 하여 빈도 수를 카운트 하였습니다.
그리고 nums[] 길이 / 2 보다 큰 Value가 나오면 반환하도록 작성하였습니다.

// HashTable
class Solution {
    public int majorityElement(int[] nums) {
        
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        
        int halfLen = nums.length/2;
        for (int num : nums){
            map.put(num, map.getOrDefault(num, 0) + 1);
            if(map.get(num) > halfLen)
                return num;
        }
        
        return 0;
    }
}

시간 복잡도: O(n)
공간 복잡도: O(n)

5. 개선 사항

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

HashTable를 활용하여 문제를 풀고 다른 개발자의 코드를 확인했는데 문제 해석을 정말 잘 하여 구현한 것 같아 배울점이 많은 것 같습니다.
문제에서 최빈값은 ⌊n / 2⌋보다 더 많이 나타나는 요소입니다라고 하면 정렬을 했을 경우 최소 절반에 위치해 있는 값이거나 그 이상의 위치에 있는 값을 말하기 때문에 절반에 있는 값을 확인하면 최빈값이 나오게 되는 것입니다.