[LeetCode] Java - Majority Element 풀이 방법

LeetCode 5월 - Day 6 Majority Element입니다.

5월은 대부분 쉽게 출제되는 것 같네요.

아무래도 Easy 정도의 문제로 보입니다.

 

오늘도 두 개의 풀이 방법입니다.

 

1. 문제

간단하게 문제를 이해해보겠습니다.

주어진 Integer 배열의 size를 n이라고 할 때 n/2한 값보다 많이 존재하는 수를 구하시오.

 

해당 수는 항상 존재한다 이것이 포인트입니다.

 

2. 풀이

풀이 방법 1

class Solution {
    public int majorityElement(int[] nums) {
        int n = nums.length/2;   
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i=0; i<nums.length; i++){
            if(map.containsKey(nums[i])){
                int count = map.get(nums[i]) + 1;
                if(count > n) return nums[i];
                else map.replace(nums[i], count);
            }else{
                map.put(nums[i], 1);
            }
        }
        
        return nums[0];
}

고민 없이 바로 코드를 작성했을 때 hashMap을 이용하면 되겠다 생각했어요.

HashMap은 key의 값을 꺼낼 때 hash 값 중복이 없다면 O(n)이 보장되기 때문에 사용했습니다.

nums의 사이즈만큼 돌면서 value 값이 2/n보다 크면 리턴하는 방식입니다.

 

 

풀이 방법 2

class Solution {
    public int majorityElement(int[] nums) {
        int r = nums[0], c = 1;
        for(int i=1; i<nums.length; i++){
            if(nums[i] == r) c++;
            else{
                c--;
                if(c == 0){
                    r = nums[i+1];
                    c = 1;
                    i++;
                }
            } 
        }
        return r;
    }
}

가장 빠른 방법일 것 같습니다.

잘 생각해보면 2/n이상 존재하는 수는 2개 중 하나는 무조건 해당 숫자가 존재하는 것을 알 수 있습니다.

그래서 처음부터 nums[0]부터 숫자를 세면서 0이 되지 않는 다면 해당 수가 정답이고 

만약 0이 된다면 이 수는 정답이 아니기 때문에 다음 수를 체크합니다.

 

문제를 잘 이해하고 패턴을 찾았다면 위 코드로 문제를 풀 수 있겠네요.