[Java] 169. Majority Element

문제 파악

 

크기가 n인 배열 nums 가 주어진다.

 

n/2 보다 많이 등장하는 수를 반환해야한다.

 

---

풀이

 

1️⃣ 해시 활용

바로 간단하게 떠오른 풀이이다.

 

먼저, 배열을 순회하면서 원소를 key 값으로 원소가 나타난 횟수를 value 값으로 map에 기록한 뒤,

 

map을 한번 더 순회하면서, 나타난 횟수가 n/2 보다 큰 경우 반환하는 방식이다.

 

import java.util.*;

class Solution {
    public int majorityElement(int[] nums) {
        int n = nums.length;
        int result = nums[0];
        HashMap<Integer, Integer> map = new HashMap<>();

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

        for (Integer key : map.keySet()) {
            if (map.get(key) > n / 2) {
                result = key;
                break;
            }
        }

        return result;
    }
}

 

결과

 

이 방식은, 시간 복잡도 O(N) 그리고 공간 복잡도도 O(N) 방식이 된다.

 

이런 문장이 있어서, 공간 복잡도를 O(1) 내로 해결할 수 있는 방법을 고민해보았다.

 

 

2️⃣ O(1) 공간 복잡도 풀이

 

혼자 해답을 고민해보다가, 도저히 아이디어가 떠오르지 않아서 다른 답을 참고해보았다.

 

아이디어는, 우리가 구해야하는 수는 n/2 보다 큰 횟수로 등장하는 수이다.

 

따라서, 배열을 순회하면서 원소를 카운팅하는데

 

다른 원소가 나오면 카운팅을 -1 해준다.

 

카운팅 값이 0이 되면, 카운팅하는 원소를 교체해준다.

 

결과적으로 카운팅하는 원소가 답이 된다.

 

import java.util.*;
class Solution {
    public int majorityElement(int[] nums) {
        int num = nums[0];
        int cnt = 0;
    
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == num) {
                cnt++;
            } else {
                cnt--;
                if (cnt == 0) {
                    num = nums[i];
                    cnt = 1;
                }
            }
        }

        return num;
    }
}

 

이 풀이는, 직관적으로는 이해가 되는데 수학적으로 잘 이해가 되지 않았다.

 

따라서 검색해보니, Boyer-Moore 과반수 투표 알고리즘이라는 이름으로 알고리즘이 존재했다.

 

배열 내에 절반이 넘는 수에 해당하는 원소가 보장이 되면 사용할 수 있는 알고리즘이라고 한다.

 

결과

---

 

📖 회고

문제가 너무 간단해서 금방 끝낼 수 있을 줄 알았는데,

 

공간 복잡도를 개선하는 방법을 떠올리느라 거의 1시간 30분을 붙잡았다.

 

그래도 오래 고민해본 만큼, 개선 방법이 머릿속에 오랫동안 남아있을 것 같다.

 

💡 "과반수 요소의 등장 횟수가 나머지 요소들의 등장 횟수를 상쇄시키는 경우"를 이용한 것

 

위 아이디어를 머릿속에 넣어두면, 나중에 쉽게 떠올릴 수 있을 것 같다.