169. Majority Element

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

주어진 조건

• 정수 배열 nums, nums의 길이 n

• n == nums.length

• 1 <= n <= 5 * 104

• 109 <= nums[i] <= 109

문제

• n/2 번 이상 나타나는 요소 return

---

나의 풀이

처음에는 따로 배열을 하나 생성해서 거기에 요소별 출현 횟수를 저장할까 했었는데, 따로 배열을 생성하지 않는 방법이 있을까 고민하다가, 주어진 nums를 정렬하는 방법이 떠올랐다.

• 먼저 nums를 오름차순으로 정렬한다. (같은 값은 한 부분에 몰려있게 된다)
• 따라서 for문을 반복 수행하면서, 이전 값과 현재 값이 같은 값이라면 계속 count를 증가시킨다.
• 만약 값이 다르다면, count 값을 검사해 n/2 보다 크다면, 이전 값을 return 하도록 했다.

구현 코드

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        nums.sort()
        n = len(nums)
        count = 1
        for i in range(1, n):
            if nums[i] != nums[i-1]:
                if count >= n/2:
                    return nums[i-1]
                else:
                    count = 1
            count += 1
        
        return nums[n-1]

• nums.sort() → O(nlogn)
• 이후의 for문 → O(n)

O(nlogn)의 시간복잡도를 가지고 있다.

---

다른 풀이 1

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        nums.sort()
        n = len(nums)
        return nums[n//2]

앞서 봤던 나의 풀이에서 내가 한 가지 간과한 점이 있었다 ..!!

정렬을 해놓으면 n/2 번 이상 나타나는 요소는 무조건 nums[n//2]에 존재할 수 밖에 없다.. 따라서 정렬 후에 return nums[n//2] 를 해주면 됐었다.

따라서 앞선 내 풀이와 비교하면 정렬 이후의 for문 실행 시간만큼 실행 시간이 감소된다.

다른 풀이 2 - **Moore Voting**

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count = 0
        candidate = 0
        
        for num in nums:
            if count == 0:
                candidate = num
            
            if num == candidate:
                count += 1
            else:
                count -= 1
        
        return candidate

• count와 candidate 변수를 0으로 초기화
• nums 안의 숫자를 반복 실행
  • 만약 count가 0이라면 현재 값을 candidate에 할당
  • 현재 요소가 candidate와 같으면 count +1
  • 현재 요소가 candidate와 다르면 count -1

Boyer-Moore 과반수 투표 알고리즘

배열에 포함된 원소들 중 절반 이상 포함도니 원소를 linear time과 constant space로 찾을 수 있는 알고리즘이다. 딱 이 문제가 원하는 구현 방식이다.

y축은 count 값이고, x축에 있는 도형이 배열에 있는 원소이다.