[LeetCode 169] Majority Element - 보이어-무어 투표 알고리즘 (Boyer-Moore Voting Algorithm) 풀이

[LeetCode] Majority Element - 보이어-무어 투표 알고리즘 (Boyer-Moore Voting Algorithm) 풀이

문제 설명

LeetCode의 "Majority Element" 문제는 배열에서 과반수 요소(majority element)를 찾는 문제입니다.

과반수 요소는 배열 길이 n의 절반(⌊n / 2⌋)을 초과하여 등장하는 요소입니다. 문제에서 항상 과반수 요소가 존재한다고 보장되므로, 이를 활용하여 최적화된 방법을 사용할 수 있습니다.

---

처음 문제를 풀었을 때의 생각

처음에는 각 숫자의 등장 횟수를 카운트해서 가장 많이 등장하는 숫자를 찾으면 되겠다고 생각했어요. 하지만 직접 구현해 보니 추가적인 메모리를 사용해야 했고, 더 최적화할 방법이 필요했습니다.

이 문제에서는 추가 메모리 없이 O(N) 시간 복잡도로 해결 가능한 보이어-무어 투표 알고리즘(Boyer-Moore Voting Algorithm)을 활용할 수 있습니다.

---

비효율적인 접근 방식 (카운팅을 활용한 풀이)

export function majorityElement(nums: number[]): number {
  const counts: Record<number, number> = {};

  for (const n of nums) {
    counts[n] = (counts[n] || 0) + 1;
  }

  return Object.keys(counts)
    .map(Number)
    .reduce((a, b) => (counts[a] > counts[b] ? a : b));
}

✅ 시간 복잡도 O(N)
❌ 공간 복잡도 O(N) (추가 해시맵 사용)

이 방법도 작동하지만, 공간 복잡도를 최적화할 방법이 필요합니다.

---

보이어-무어 투표 알고리즘 (Boyer-Moore Voting Algorithm)

이 문제는 과반수 요소가 항상 존재한다는 점을 활용하면, 투표 개념을 적용해서 공간 복잡도를 O(1)로 최적화할 수 있습니다.

✅ 보이어-무어 알고리즘 실행 과정

export function majorityElement(nums: number[]): number {
  let candidate = 0;
  let count = 0;

  for (const num of nums) {
    if (count === 0) {
      candidate = num;  // 새로운 후보 설정
    }
    count += num === candidate ? 1 : -1;  // 같으면 증가, 다르면 감소
  }

  return candidate;
}

✅ 시간 복잡도 O(N)
✅ 공간 복잡도 O(1)
✅ 배열을 한 번만 순회하며 해결 가능

---

보이어-무어 알고리즘 원리 (쉽게 이해하기)

배열을 투표하는 사람들로 생각해 보자.

• 각 숫자는 후보(candidate) 가 될 수 있음.
• 같은 숫자는 찬성표(++) 를 던지고, 다른 숫자는 반대표(--) 를 던짐.
• 과반수 요소는 항상 절반 이상 존재하므로, 최종적으로 살아남는 후보는 무조건 과반수 요소가 됨.

예제 실행 과정

nums = [2,2,1,1,1,2,2]

단계 현재 숫자 후보(candidate) 개수(count) 설명

1	2	2	1	첫 번째 요소가 후보가 됨
2	2	2	2	같은 숫자가 나와 count++
3	1	2	1	다른 숫자가 나와 count--
4	1	2	0	다른 숫자가 나와 count--, 후보 제거
5	1	1	1	새로운 후보 1 설정
6	2	1	0	다른 숫자가 나와 count--, 후보 제거
7	2	2	1	새로운 후보 2 설정

✅ 최종 후보: 2 (과반수 요소)

---

Jest 테스트 코드

describe("Majority Element - Boyer-Moore Voting Algorithm", () => {
  it("returns the majority element from an odd-length array", () => {
    const nums = [3, 2, 3];
    expect(majorityElement(nums)).toEqual(3);
  });

  it("returns the majority element from an even-length array", () => {
    const nums = [2,2,1,1,1,2,2];
    expect(majorityElement(nums)).toEqual(2);
  });

  it("handles an array where all elements are the same", () => {
    const nums = [5, 5, 5, 5, 5, 5, 5];
    expect(majorityElement(nums)).toEqual(5);
  });
});

✅ it 설명을 명확하게 추가하여 테스트의 목적을 알기 쉽게 정리
✅ 다양한 테스트 케이스 추가

---

결론

처음에는 배열을 순회하며 카운팅하는 방식을 생각했지만, 공간 복잡도를 최적화할 필요가 있었습니다.

보이어-무어 투표 알고리즘은 과반수 요소가 항상 존재한다는 점을 이용하여 최적화할 수 있었습니다. 🎯

이제 과반수 요소를 찾는 문제를 만나면 보이어-무어 알고리즘을 활용해 보세요! 🚀