[Dart] 169. Majority Element (Boyer-Moore VoitingAlgorithm)

1. 문제

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

 

 

 

 

2. 요구사항

1) 주어진 배열에서 majority element를 찾는 문제이다.

2) majority element는 배열의 원소 중 절반 이상의 개수를 차지하는 원소를 의미한다.

3) 최빈값을 찾아야 하며, 최빈값이 존재하는 것이 항상 보장된다.

 

 

 

3. 핵심 아이디어

1) 투표 알고리즘 (Boyer-Moore VoitingAlgorithm)

배열에 포함된 원소들 중 절반 이상 포함된 원소를 찾는 시간 복잡도 O(n), 공간 복잡도 O(1)을 갖는 알고리즘이다.

 

과반수를 가진 숫자는 나머지 숫자들과 1:1로 제거해도 결국 살아남는다.

 

알고리즘 로직은 다음과 같다.

해당 숫자가 몇개 나왔는지를 세는 count 변수를 선언한 후,

후보(candidate)를 배열의 첫번째 숫자로 시작한다.

 

같은 숫자가 나오면 count에 1을 더하고,

다른 숫자가 나오면 count에 1을 뺀다.

 

만약, count가 0이면 새로운 후보로 교체한다.

 

 

https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm

 

 

 

2) 코드

class Solution {
  int majorityElement(List<int> nums) {
    int count = 0;
    int candidate = nums[0];

    for(int i = 0; i < nums.length; i++) {
        if(count == 0) {
            candidate = nums[i];
        }
        
        // 현재 숫자가 candidate과 같으면 count 증가, 다르면 감소
        count += (nums[i] == candidate) ? 1 : -1; 
    }

    return candidate;
  }
}

 

시간 복잡도 : O(n)

공간 복잡도 : O(1)