[LeetCode] 169. Majority Element

leetcode.com/problems/majority-element/

Majority Element - LeetCode

 

해시맵 중독..해시맵으로 문제 풀기 완료

Given an array nums of size n, return the majority element.
The majority element is the element that appears more than ⌊n / 2⌋ times.
You may assume that the majority element always exists in the array.

• n개 요소를 가진 nums 배열에서 majority element는 n/2 번 보다 많이 존재할 경우로 판단
• majority element는 배열에 항상 존재하는 것으로 가정
  

public class MajorityElement0319 {

    public int majorityElement(int[] nums) {
        int majorElement = 0;

        //for문을 돌며 배열을 담는다. {숫자:개수}
        Map<Integer,Integer> map = new HashMap<>();
        for(int i=0;i<nums.length;i++){
            // 처음 담는 숫자가 아니라면
            if(map.get(nums[i])!=null){
                map.replace(nums[i], map.get(nums[i])+1);
                System.out.println("i="+i+map);
            }else {
                map.put(nums[i],1);
                System.out.println("i="+i+map);
            }

            //majority element 찾기
            if(map.get(nums[i])>(nums.length/2)){
                majorElement = nums[i];
            }
        }//for

        return majorElement;
    }

}

처음 담는 숫자면 {숫자:1}을 저장하고, 이미 있는 숫자라면 value 값을 대체하는 것으로 코드를 작성했다.

어차피 map은 key값의 중복을 허용하지 않으니 repalce 대신에 put을 써줘도 되지 않을까 생각했는데, 찾아보니 repalce 보다 put을 더 자주 사용하는 듯 하다. 실무에서는 어떨 지 궁금하다.

 

런타임 13ms

아무래도 map에 담는 과정이 있다보니 런타임이 길어진다. 

다른 간편한 방법이 분명히 있을거라 생각하고 솔루션을 살펴봤다.

---

간결하고 빠른 정답

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

런타임 1ms

높은 문제 이해도 + 규칙을 빨리 파악하는 사람은 이렇게 푸는 걸까? 놀라웠다.

 

배열의 인덱스 개념을 활용한 것인데, 먼저 배열을 오름차순 혹은 내림차순으로 정렬하고

배열 length가 n일때, 요소의 절반이상은 majority element 로 이루어져 있다는 규칙을 이용한 풀이이다.

 

1. n이 홀수라면 (예 n=7) majority element 요소는 배열에 최소 4개가 있을 것이고, index=3인 경우에 majority element 값을 얻을 수 있다.

 

2. n이 짝수라면 (예 n=6) element 요소는 배열에 최소 4개가 있을 것이고, index=2 또는 index=3인 경우에 majority element 값을 얻을 수 있다.

 

이처럼 n의 홀수/짝수 여부에 상관없이 nums.length/2 번째에 있는 값은 항상 majority element 값임을 알 수 있다.

 

출처 : LeetCode

 

---

그 외에도 아주 다양한 풀이가 있었다. 

코테를 풀다보면 정말 신기하고 배울 내용이 엄청 많다고 매번 느낀다. 🔥📚