[LeetCode] 169번 (Majority Element)

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

Majority Element - LeetCode

---

🤣 문제 설명

• n 크기의 정수 배열 nums 가 주어진다.
• nums 의 요소들 중 빈도수가 제일 높은 즉 빈도수가 n/2 이상인 요소 값을 찾아 반환한다.
• 추가로 공간 복잡도의 크기는 O(1)이다.

 

🥲 문제 해결

• 정수 배열을 오름차순으로 정렬한다. (같은 값은 순서대로 묶여있을 것이다.)
• nums 를 순환하면서 해당 인덱스 값과 해당 인덱스에 n/2 를 더한 값을 비교한다.
• 같은 경우는 최다 빈도수를 가지는 값이다. (n/2 이상이기 때문)

 

😊 시간 복잡도

최악의 경우에 O(n^2) 이며 평균은 O(nlogn)이다. (정렬 부분)

이 부분이 미스였던 것 같다. O(n/2) 로 줄일 수 있다고 판단해 해당 알고리즘을 구현했지만, 정렬이 차지하는 시간 복잡도는 생각하지 못 했다. n의 최대 크기가 50000 이므로 최악의 경우 O(2500000000) 이므로 시간 초과가 발생할 확률이 있다.

 

🙂 공간 복잡도

O(1) 이다.

O(1) 조건을 맞추기 위해 정수 배열을 리스트로 변환해 시간복잡도가 최악의 경우에 O(nlogn) 인 Collections.sort() 을 사용하지 못했다.

 

😌 정답

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        int h = nums.length / 2;
        int result = 0;

        for(int i = 0; i<h+1; i++) {
            if(nums[i] == nums[i+h]) {
                result = nums[i];
            }
        }
        return result;
    }
}

 

😗 개선사항

• 나름 효율적인 알고리즘으로 짰다고 생각했지만, 정렬에 들어가는 시간을 계산하지 못했던 미스가 크게 작용했다.
• 정렬하지 않고 과반수 득표 알고리즘을 사용하면 시간 복잡도는 O(n) 으로 공간 복잡도는 O(1)로 작성할 수 있다.

class Solution {
    public int majorityElement(int[] nums) {
        int x = 0;
        int count = 0;

        for (int num : nums) {
            if(count == 0) {
                x = num;
                count++;
            } else if (x == num) {
                count++;
            } else {
                count--; //과반수가 넘어가면 x 값이 바뀌게끔 설정
            }
        }
        return x;
    }
}