Today I Learned

오늘도 코테 공부!

---

169. Majority Element

https://leetcode.com/problems/majority-element/description/

문제

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.

Example:
Input: nums = [2,2,1,1,1,2,2]
Output: 2

• Follow-up: Could you solve the problem in linear time and in O(1) space?

---

풀이 과정 & Java 코드

• 그냥 풀기는 쉬운 문제이지만, follow-up에서 제안한 O(n)의 시간복잡도와 O(1)의 공간복잡도로 문제를 푸는 방법은 쉽지 않았기에 정리해보았다.

1. Sort

  public int majorityElement(int[] nums) {
    int len = nums.length;
    if (len==1) return nums[0];
    Arrays.sort(nums);
    int ans = 0;
    int c = 0;
    for (int i = 1; i < nums.length; i++) {
      if (nums[i]==nums[i-1]){
        ans = nums[i];
        c++;
        if (c>=len/2) return ans;
      } else {
        c = 0;
        ans = nums[i];
      }

    }
    return -1;

  }

• 배열을 sort 한 뒤 앞 뒤 원소를 비교해 일치하면 count를 올리고 그 카운트가 과반수를 넘어가면 해당 숫자를 반환하는 방식이다.

• 나쁘지 않은 결과지만 sort에서 이미 O(n log n)이 소모되기 때문에 다른 방법을 찾아야 했다.

---

2. HashMap

    public static int majorityElement(int[] nums) {
        Map<Integer, Integer> countMap = new HashMap<>();

        for (int num : nums) {
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        }

        int majorityElement = 0;
        int maxCount = 0;

        for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
            if (entry.getValue() > maxCount) {
                majorityElement = entry.getKey();
                maxCount = entry.getValue();
            }
        }

        return majorityElement;
    }

• 해시맵을 하나 만들어 원소를 key로 삼고, 나온 횟수를 value로 해서 저장해 가장 많이 나온 value를 찾는 방식이다.

• sort가 필요없고, 시간 복잡도 O(N)과 공간 복잡도 O(N)을 가지며, 과반수가 아니더라도 적용할 수 있는 장점이 있다.(애초에 코드를 그렇게 짰다.)

---

3. boyer-moore voting algorithm

    public static int majorityElement(int[] nums) {
        int candidate = 0;
        int count = 0;

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

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

        return candidate;
    }

• 아주 간단한 방법으로 시간복잡도 O(N), 공간복잡도 O(1) 만으로 과반수의 원소를 찾을 수 있는 방법이다.

• 후보와 횟수 변수를 하나씩 선언해두고, for문을 한번만 돈다.
  후보의 숫자와 순회하는 원소가 같으면 count를 증가하고, 다르면 count를 낮춘다. 이렇게 한번 순회하면 과반수의 원소가 candidate에 저장된다.
  단, 과반수가 아니면 적용할 수 없다.