.leetcode(169. Majority Element)

문제

leetcode.com/problems/majority-element

Majority Element - LeetCode

문제 풀기 전

1. 숫자를 세는 문제이기때문에 HashMap이 가장 먼저 떠올랐다. O(n)시간이 걸릴것이다.
2. 뭔가 옛 기억이 PriorityQueue를 사용하면 될거같은데 잘 모르겠다.

직접 푼 풀이

소요시간: 11분(09:40 ~ 09:51)

class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> counter = new HashMap<>();
        for(int each: nums) {
            if (counter.containsKey(each)) {
                counter.put(each, counter.get(each) + 1);
            } else {
                counter.put(each, 1);   
            }
        }

        int maxKey = 0;
        int maxValue = 0;
        for (Map.Entry<Integer, Integer> entrySet: counter.entrySet()) {
            if (maxValue < entrySet.getValue()) {
                maxValue = entrySet.getValue();
                maxKey = entrySet.getKey();
            }
        }

        return maxKey;
    }
}

느낀점

1. 문제의 단서를 좀 더 확인했으면 Sorting 풀이에서 접근할 수도 있었는지 모른다. 아래 답 참고한 Sorting풀이는 기막히다.
2. Divide and Conquer 방식으로도 풀 수 있는데 중점을 잡고 계속 분할한다음 해결하는 방법인데 이해가 잘 안되었다. 이건 구지 이렇게 풀었어야 하나 싶고 다음에 Divide and Conquer문제가 나올때 제대로 다루어 보면 좋겠다.
3. Boyer–Moore majority vote algorithm에 대해 배울 수 있었다. 이 알고리즘은 제약조건이 있다. 전체 과반수 초과되는 수를 하나의 숫자가 갖고 있다는 전제하에서만 실행이 될 수 있다. 그런 전제가 있다면 언제가 과반수 초과하는 숫자는 다른 숫자들을 감싸안는 형태의 배열이 나올 수 밖에 없다. 증명을 하기 위해서는 최악의 경우를 생각해볼 수 있다. 홀수개의 요소를 갖고 있는 배열을 생각해보자.

• 홀수개를 확인하기 위해 3개의 요소를 갖고 있는 배열을 생각해보고 거기다가 count가 최대한 증가하지 않게 하기 위한 최악의 배열을 우리가 만들어 볼 수 있다.
• [1,2,1] 이렇듯 홀수개인 경우, 과반의 수를 넘는 숫자는 늘 최외곽을 감싸안는 형태가 되므로 성립할 수 밖에 없다.
• 짝수개는 홀수개보다 과반수 기준이 엄격하다. (n/2)초과하는 과반수를 가져야하므로 늘 홀수개보다 한개많은 과반의 수를 갖게 되고 홀수개가 되므로 짝수개도 당연히 된다고 볼 수 있다.
• 실제 코드는 아래와 같다.

솔루션 공부 후 추가로 푼 풀이

#Sorting을 이용한 풀이
class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);

        int maxNum = 0;
        int count = 0;
        int max = 0;
        Integer prev = null;
        for(int each: nums) {
            if (prev != null && prev != each) {
                if (count > max) {
                    max = count;
                    maxNum = prev;
                }
                count = 1;
            } else {
                count++;
            }
            prev = each;
        }

        if (count > max) {
            max = count;
            maxNum = prev;
        }

        return maxNum;
    }
}

#Sorting의 기막힌 활용 풀이(답 참고)
class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }
}

# Boyer–Moore majority vote algorithm
class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        Integer candidate = null;

        for (int each: nums) {
            if (count == 0) {
                candidate = each;
            }

            count += (each == candidate ? 1: -1);
        }

        return candidate;
    }
}

누적되는 알고리즘 접근 설명서

1. 제한값이 있는지 확인한다.

2. 최대 시간복잡도나 최대 경우의 수를 유추해본다.

3. 기본으로 주어지는 메소드에서 해결이 가능한지 생각해본다. > 메소드를 만들어 사용한다. > 전역변수를 과감히 도입한다.

4. recursion(Brute Force, Back Tracking)으로 가능할지 먼저 생각해본다. 이 후에 iterative하게 풀 수 있을지도 생각해본다. iteratvie하게 풀때는 stack을 이용해본다. 경우의 따라 queue를 사용해볼 수 있다.

5. recursion일 경우, 종료조건을 먼저 만들고 로직을 만든다.

6. 주어진 Input데이터를 더렵힐 수도 있다고 생각해본다. 덮어쓰기한다던지, 더해서 합값으로 치환한다던지 말이다.

7. TreeNode는 left,right,val으로 구성해볼 수 있고 ListNode는 val,next로 구성해볼 수 있다.

8. ListNode문제가 나오면 꼭 그림으로 next관계를 이해해보자

9. 배열에서 갯수를 센다고 하면 Brute force, HashMap, Sorting방법을 생각해보자.

10. 만약에 대다수를 구하는 문제라면 Boyer–Moore majority vote algorithm를 생각해보자.

나중에다시한번

• Divide and Conquer 로 풀어보기
• PriorityQueue로 접근해보기