[2024] day 43. 169. Majority Element

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 2월 12일 (월)
Leetcode daily problem

169. Majority Element

https://leetcode.com/problems/majority-element/description/?envType=daily-question&envId=2024-02-12

Problem

정수 원소로 구성된 크기가 n인 배열 nums가 주어질 때 해당 배열에서 가장 주가 되는(많은 빈도를 차지하는) 원소를 반환한다.
주가 되는 원소는 n/2 회 보다 많이 나올 경우 주원소로 판단한다.
배열에 주 원소는 항상 존재한다.

Solution

Boyer-Moore Voting Algorithm

반복문을 통해 배열을 탐색하면서 현재의 원소를 후보로 지정한다.
빈도를 할당하는 major를 사용해 현재 원소의 등장 횟수를 추적하면서 업데이트 한다.
만약 major가 0이라면, 현재 후보로 새로운 요소로 업데이트하고,
현재 요소와 후보 요소가 같다면, major를 증가시킨다. 다르다면, major를 감소시킨다.
최종적으로 카운터 변수 major가 0이 아닌 요소가 과반수 이상을 차지하는 요소가 된다.

Code

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        ans, major = 0, 0

        for num in nums:
            if major == 0:
                ans = num

            major +=1 if num==ans else -1

        return ans

Complexicity

시간 복잡도

주어진 nums의 배열을 탐색할 때 O(n)이 소요된다.

공간 복잡도

각 변수들은 상수만 할당하기 때문에 O(1) 이다.

---

처음 Counter를 사용해서 풀었을 때는
counter 함수를 사용해서 O(n)이 소요되고, 이를 정렬하는 과정에서 O(nlogn)으로 총 시간복잡도는 O(nlogn)이었고 공간복잡도는 counter를 함수로 원소에 해당하는 빈도를 담는 O(n)이었다.

이를 최적화해서 공간복잡도를 O(1)로 해결하는 방법은 major 변수로 나오는 빈도들의 +,- 해가면서 최종 원소의 값이 담길 ans를 업데이트 하는 방법이다.