[LeetCode] 169. Majority Element - Java[자바]

링크

문제

크기가 n인 배열의 숫자가 주어지면 다수 요소를 반환합니다.

다수 요소는 ⌊n / 2⌋ 이상 나타나는 요소입니다. 다수 요소는 배열에 항상 존재한다고 가정할 수 있습니다.

풀이

import java.util.*;  
import java.util.Map.*;  
  
class Solution {  
    public int majorityElement(int[] nums) {  
        Map<Integer, Integer> map = new TreeMap<>();  
        for (int num : nums) {  
            map.merge(num, 1, Integer::sum);  
        }  
        int maxKey = -1;  
        int maxValue = -1;  
        for (Entry<Integer, Integer> entry : map.entrySet()) {  
            if (maxValue < entry.getValue()) {  
                maxValue = entry.getValue();  
                maxKey = entry.getKey();  
            }  
        }  
        return maxKey;  
    }  
}

당장 떠오른 풀이는 위와같이 nums에 Map을 통해서 최빈값을 찾는 풀이가 떠올랐다.

아니면 nums[i]의 범위에 따라서 정적 int 배열을 만들어 똑같이 map 처럼 사용하는 방식도 고려했다. 하지만, nums[i] 의 범위는 int 값을 벗어나므로 정적 배열을 사용할 수는 없다.

다른 풀이

majority에 대해서 단순하게 최빈값이라고 생각했는데, 문제를 다시 읽어보니 최빈값 이전에 배열의 길이가 n이라면, n/2번 이상 등장하는 값임을 알게 되었다.

이에 따라 인사이트를 얻은 것은, 배열을 정렬하게 되면 문제에서 요구하는 majority 원소의 경우 항상 n/2 index에도 존재하게 된다는 점이었다.

풀이는 단순하게 주어진 배열을 정렬하고 n/2값을 return 하면 되므로 생략한다.