[LeetCode] - 169. Majority Element

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '쉬움 (Easy)' 단계인 "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 1 :

Input : nums = [3,2,3]

Output : 3

 

Example 2 :

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

Output : 2

 

Constraints :

• n == nums.length
• 1 <= n <= 5 * 10^4
• -10^9 <= nums[i] <= 10^9

 

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

 

---

주어진 배열 nums에서 과반수 요소를 찾는 문제입니다. 과반수 요소는 배열의 절반을 초과하여 등장하는 요소를 의미합니다. 문제에서는 항상 과반수 요소가 존재한다고 가정하고 있습니다.

class Solution {
    public int majorityElement(int[] nums) {
        int maj = (nums.length / 2);
        Map<Integer, Integer> countMap = new HashMap<>();
        for (int num : nums) {
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        }

        for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
            if (entry.getValue() > maj) {
                return entry.getKey();
            }
        }
        return -1;
        
    }
}

 

이 코드는 주어진 배열 nums에서 과반수 요소를 찾기 위해 해시맵을 사용하는 방법을 구현합니다. 해시맵은 각 요소의 빈도를 저장하고, 빈도가 n/2를 초과하는 요소를 찾습니다.

1. 과반수 기준 설정 :
   • maj 변수는 배열 길이의 절반을 의미합니다. 과반수 요소는 이 값보다 큰 빈도를 가져야 합니다.
2. 해시맵 초기화 :
   • countMap은 각 요소의 빈도를 저장하기 위한 해시맵입니다.
3. 요소 빈도 계산 :
   • 배열 nums를 순회하며 각 요소 num의 빈도를 계산하여 해시맵에 저장합니다.
   • countMap.getOrDefault(num, 0) + 1는 요소 num의 현재 빈도에 1을 더한 값을 저장합니다. 만약 num이 해시맵에 없으면 기본값 0을 사용합니다.
4. 과반수 요소 찾기 :
   • 해시맵의 모든 엔트리를 순회하며 각 요소의 빈도가 maj보다 큰지 확인합니다.
   • 빈도가 maj보다 큰 요소를 찾으면 해당 요소를 반환합니다.
5. 결과 반환 :
   • 문제의 조건에 따르면 항상 과반수 요소가 존재한다고 가정하므로 이 부분은 사실 실행되지 않습니다. 하지만 안전을 위해 존재하는 코드입니다.

• 시간 복잡도 : O(n)
  • 배열 nums를 한 번 순회하며 각 요소의 빈도를 계산하는데 O(n) 시간이 소요됩니다.
  • 해시맵의 엔트리를 순회하여 과반수 요소를 찾는 과정도 O(n)입니다.
  • 따라서 전체 시간 복잡도는 O(n)입니다.
• 공간 복잡도 : O(n)
  • 해시맵 countMap은 최대 n개의 키-값 쌍을 가질 수 있으므로 공간 복잡도는 O(n)입니다.

---

솔직히 이 문제에 있어서 시간 복잡도는 조금 더 올라가지만 사기적인 코드가 있습니다 : 

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

 

바로 이 코드인데, 처음부터 Arrays.sort()를 하여 정렬을 한 후에 nums의 길이의 반인 인덱스를 리턴하는 코드입니다.

 

• 시간 복잡도 : O(n log n)
  • Arrays.sort(nums);는 O(n log n)의 시간 복잡도를 가지며, 이 부분이 전체 알고리즘의 시간 복잡도를 결정합니다.
• 공간 복잡도 : O(1) 또는 O(n) --> 그래서 아마 전 코드 보다 조금 더 효율적이라고 생각될 수도 있습니다. 
  • Java의 기본 정렬 메서드(Arrays.sort)는 일반적으로 내부적으로 O(1)의 추가 공간을 사용하지만, 병합 정렬을 사용할 경우 O(n)의 공간 복잡도를 가질 수 있습니다.
  • Arrays.sort는 Dual-Pivot Quicksort를 사용하여 O(1)의 추가 공간을 사용합니다.

---

 

다른 유저들 코드를 보니 아예 이 문제를 풀기 위한 전담 풀이 방식이 있었습니다. 이름은 : 

Moore Voting 방법이라는데, 코드는 이랬습니다 : 

class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        int candidate = 0;
        
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            
            if (num == candidate) {
                count++;
            } else {
                count--;
            }
        }
        
        return candidate;
    }
}

// rahulvarma5297 유저의 코드

 

이 유저분도 설명을 친절하게 해 주셨는데, 영어로 너무 긴 거 같아서 제가 요약해 드리겠습니다 : 

 

핵심 아이디어 : 과반수 요소는 배열의 절반을 초과해서 나타나기 때문에, 다른 요소들과 비교해도 결국 최종적으로 가장 많이 남게 됩니다.

1. 변수 초기화 :
   • candidate와 count를 초기화합니다. count는 0으로 설정하고, candidate는 초기 후보로 설정합니다.
2. 배열 순회 :
   • 배열의 각 요소에 대해 :
     • count가 0이면, 현재 요소를 새로운 후보(candidate)로 설정하고 count를 1로 설정합니다.
     • 현재 요소가 candidate와 같으면 count를 1 증가시킵니다.
     • 현재 요소가 candidate와 다르면 count를 1 감소시킵니다.
3. 결과 반환 :
   • 반복이 끝난 후, candidate는 과반수 요소가 됩니다.

올바름의 이유

• 과반수 요소는 배열의 절반 이상을 차지하므로, 다른 요소들이 count를 0으로 만들더라도 최종적으로 다시 후보가 됩니다.

 

• 시간 복잡도 : O(n)
  • 배열을 한 번만 순회합니다.
• 공간 복잡도 : O(1)
  • 추가 공간을 사용하지 않습니다.

효율성

• 정렬 사용 방법보다 효율적 :
  • 정렬은 O(n log n)이지만, 이 알고리즘은 O(n)으로 더 빠릅니다.
  • 배열의 순서를 변경하지 않으며 상수 공간을 사용하여 효율적입니다.

---

코드 순서대로 Runtime 결과