[오늘의 코테연습장][LeetCode] 169. Majority Element

🔖 문제

• 크기가 n인 배열 nums가 주어졌을 때, 과반수 요소를 반환하세요.

• 과반수 요소란 ⌊n / 2⌋보다 많이 등장하는 요소를 의미합니다.

🔖접근 방식

문제를 보자마자 HashMap을 이용하여 요소와 요소의 등장 빈도수를 저장해야겠다는 생각이 들었습니다.
또한 이 문제를 해결하는 과정에서 새롭게 알게 된 stream().max(Map.Entry.comparingByValue()) 함수를 사용하여, Map.Entry 객체들 중 value 값이 가장 큰 값을 찾았습니다.

1. numsMap이라는 새로운 HashMap을 생성합니다.
2. numsMap에 요소와 요소의 등장 빈도수를 저장합니다.
3. numsMap.entrySet().stream()을 호출하여, numsMap의 entrySet을 스트림 형태로 변환합니다.
4. .max(Map.Entry.comparingByValue())를 호출하여 스트림의 각 요소들을 value 값(빈도수)을 기준으로 비교하며 최대 값을 찾습니다.
   5.최대 빈도수를 가진 Key 값을 반환합니다.

🔖문제 풀이 코드

import java.util.*;
class Solution {
    public int majorityElement(int[] nums) {
     // HashMap 사용해서 integer, 빈도수 저장
     // 빈도수가장높은 key 출력
     int answer =  0 ;
     HashMap<Integer, Integer> numsMap = new HashMap<Integer,Integer>();
     for(int num : nums){
        numsMap.put(num, numsMap.getOrDefault(num,0)+1);
     }
   
     Optional<Map.Entry<Integer, Integer>> maxEntry =numsMap.entrySet().stream().max(Map.Entry.comparingByValue());
    return  maxEntry.get().getKey();
}
}

🔖다른 접근방식

처음에 이 문제를 접하고 나서 해결까지 꽤 시간이 걸렸습니다.
단순한 문제처럼 보이는데 이문제처럼 빈도수가 등장하는 문제라면 항상 HashMap을 이용해서 풀었기 때문에, HashMap을 이용해서 풀어야한다는 생각에, HashMap을 이용해 처리하는 과정을 작성하느라 오래걸렸습니다.

문제를 해결한 후, 다른 사람들의 코드를 봤는데

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

많이 단순하게 풀수 있는 문제습니다.

nums를 오름차순으로 정렬한후,
nums 배열을 오름차순으로 정렬한 후, 배열의 중간 위치에 있는 요소를 반환하면 과반수를 차지한 요소 값을 얻을 수 있습니다.

앞으로는 좀더 단순하게 생각해보는 연습도 해봐야겠습니다.