Week 1-1. [Array / String] 169. Majority Element

문제 해결 과정

✍️ 나만의 방식으로 문제 정리하기 (=체계화)

https://leetcode.com/problems/majority-element/?envType=study-plan-v2&envId=top-interview-150 

Majority Element - LeetCode

주어진 배열의 길이가 n이라고 할 때, 배열에 n/2개 이상 존재하는 원소를 반환하라.

• 입력
  • nums | int arrray := 중복된 원소가 포함된 배열, | nums | == n
• 출력
  • k | int := 배열에서 반 이상을 차지하는 원소
• 조건
  • | n | ∈ [1, 5 * 10^4]
  • | nums[i] | ∈ [-10^9, 10^9]

 

🔎 어떤 식으로 접근했는가?

해시맵을 이용해 특정 원소를 key로, 해당 원소의 빈도수를 value로 저장한다.

마지막으로 빈도수가 가장 높은 원소를 반환한다.

 

🙈 알고리즘 선택: 입력의 크기를 바탕으로

nums의 길이가 최대 50,000이므로 for문을 이용하여 하나씩 탐색해도 된다.

HashMap을 이용하여 원소와 각각의 빈도수를 저장할 것이다.

 

📝 의사 코드

hm = 숫자와 빈도수를 담을 해시맵

for (0부터, nums 끝까지, 1씩 증가) {
	key가 i인 원소의 value를 1 증가
}

해시맵에서 value가 가장 큰 key값 리턴

 

🎯 구현 코드

class Solution {
    public int majorityElement(int[] nums) {
        HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) {
            hm.put(nums[i], hm.getOrDefault(nums[i], 0) + 1);
        }

        int max_value = -1;
        int max_key = -1;
        for (Map.Entry<Integer, Integer> pair : hm.entrySet()) {
            if (pair.getValue() > max_value) {
                max_value = pair.getValue();
                max_key = pair.getKey();
            }
        }
        return max_key;
    }
}

 

내 코드를 탐구해보기

⏱ 성능 측정 (시간복잡도/공간복잡도)

단일 for문을 사용하였으므로 시간 복잡도는 O(N)이다.

 

✍️ 성능 회고

N은 최대 50,000 이므로 감당할 수 있는 범위이다.

 

💡 무엇을/어떻게 개선할 수 있을까?

현재 코드는 해시맵 전체를 순회하면서 빈도수(value)의 최대를 구한 뒤 해당 원소(key)를 리턴한다.

 

문제에서 배열 길이의 절반 이상 나타나는 원소를 리턴하라고 했으므로,

해시맵을 순회하다가 특정 원소(key)의 빈도수(value)가 n/2 이상이라면 바로 리턴하여 순회를 중단할 수 있다.

class Solution {
    public int majorityElement(int[] nums) {
        HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) {
            hm.put(nums[i], hm.getOrDefault(nums[i], 0) + 1);
        }

        int N = nums.length / 2;
        for (Map.Entry<Integer, Integer> pair : hm.entrySet()) {
            if (pair.getValue() > N) {
                return pair.getKey();
            }
        }
        return 0;
    }
}

 

다른 사람의 코드를 탐구해보기

🎯 구현 코드

nums 배열에서 반 이상 특정 원소가 등장한다면, 배열이 정렬되었을 때 해당 원소는 중간 위치를 차지한다.

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

 

⏱ 성능 측정 (시간복잡도/공간복잡도)

길이가 n인 배열을 정렬할 때의 평균 시간복잡도는 O(nlog(n))이다.

 

느낀 점

nums 배열에서 반 이상 특정 원소가 등장한다면, 배열이 정렬되었을 때 해당 원소는 중간 위치를 차지한다.

위 발상이 인상깊었다.

 

각 원소의 빈도수를 계산할 필요 없이 정렬한 뒤 중간 위치의 원소를 반환하면 간단하다.

생각해 보지 못한 아이디어를 하나씩 차곡차곡 쌓아두자! 👏