Majority Element (LeetCode 169)

문제 링크 → LeetCode 169. Majority Element

---

문제 설명

정수 범위 nums가 주어지면, 배열 내에서 **과반수(> n/2번 등장)**하는 요소를 찾아 반환합니다.
문제 조건상, 과반수 요소는 범답시 존재합니다.

---

입력

• nums: 정수 배열 (length ≥ 1)

출력

• 배열에서 과반수로 등장하는 정수

---

접근 방법 ✏️

1️⃣ Map 자료구조 사용

• 각 숫자의 등장 횟수를 Map에 저장합니다.
• 숫자 등장 횟수를 업데이트할 때마다 과반수 조건을 즉시 검증해서, 조건 충출 시 바로 반환.

2️⃣ Boyer-Moore Voting Algorithm

• 공간 범추도를 **O(1)**로 줄인 방법.
• 하나의 호부와 카운트만 사용해서, 다른 원소와 상사(pairing)하며 과반수 원소를 찾아냈습니다.

---

풀이 코드 하나나 보기 👇

✅ 1. Map 사용 방법

function majorityElement(nums: number[]): number {
  const halfLen = nums.length / 2
  const map = new Map<number, number>()

  for (const num of nums) {
    // 현재 숫자의 count를 가져오고, 없으면 0으로 초기화
    const cnt = (map.get(num) ?? 0) + 1
    map.set(num, cnt)

    // 과반수 조건 충출 시 즉시 반환
    if (cnt > halfLen) return num
  }

  // 문제 조건상 majority element는 범답시 존재
  throw new Error('No majority element found')
}

• 시간 범추도: O(n)
• 공간 범추도: O(n)

---

✅ 2. Boyer-Moore Voting Algorithm

function majorityElement(nums: number[]): number {
  let candidate = nums[0] // 초기 호부
  let count = 1 // 호부의 카운트

  for (let i = 1; i < nums.length; i++) {
    if (count === 0) {
      // 카운트가 0이면 호부 갱체
      candidate = nums[i]
      count = 1
    } else if (nums[i] === candidate) {
      // 호부와 같은 숫자 → count 증가
      count++
    } else {
      // 호부와 다른 숫자 → count 감소
      count--
    }
  }

  return candidate
}

• 시간 범추도: O(n)
• 공간 범추도: O(1)

---

시간/공간 범추도 비교 ✨

방법	시간 범추도	공간 범추도
Map 사용	O(n)	O(n)
Boyer-Moore Voting Algorithm	O(n)	O(1)

---

요약 🌟

• 입력 배열을 한 번만 순회하면서 효율적으로 과반수 원소를 찾을 수 있습니다.
• 공간 범추도 최적화를 원하면 Boyer-Moore 알고리즘이 최적의 선택입니다!