[코딩 인터뷰] LeetCode - Array/Strings - 169. Majority Element

안녕하세요, 코딩 인터뷰를 준비하시는 여러분! 오늘 다뤄볼 문제는 "169. Majority Element"입니다. 이 문제는 배열에서 가장 많이 등장하는 요소, 즉 다수의 요소를 찾는 것으로, 코딩 인터뷰에서 자주 등장하는 유형 중 하나입니다. 🎓 이 문제를 해결하기 위해서는 배열 순회부터 해시 테이블, 보이어-무어 다수결 알고리즘, 분할 정복까지 다양한 프로그래밍 개념을 이해하고 적용할 필요가 있습니다. 🧠 이 글에서는 이러한 개념들을 실제 문제에 어떻게 적용하는지 알아보겠습니다.

 

보이어-무어 다수결 알고리즘

 

---

🎯 문제 설명

"169. Majority Element" 문제는 주어진 크기의 배열 nums에서 다수의 요소(메이저리티 엘리먼트)를 찾아내는 것입니다. 메이저리티 엘리먼트는 배열 내에서 ⌊n / 2⌋번 이상 나타나는 요소를 의미합니다. 문제의 조건에 따르면, 메이저리티 엘리먼트는 항상 배열에 존재한다고 가정합니다.

예를 들어:

• 입력: nums = [3,2,3]
• 출력: 3

다수의 요소는 배열의 절반을 초과하여 나타나는 요소이므로, 이 문제를 풀기 위한 여러 가지 접근 방법을 알아보겠습니다.

 

문제 보기

---

📘 알아야 할 개념 공부하기

이 문제를 해결하기 위해 알아야 할 몇 가지 중요한 개념이 있습니다:

• 배열 순회: 배열의 각 요소를 접근하는 방법을 익혀야 합니다.
• 해시 테이블: 요소의 출현 횟수를 기록하는 데 유용합니다.
• 보이어-무어 다수결 알고리즘: 가장 효율적인 방법 중 하나로, 배열을 한 번만 순회하면서 다수의 요소를 찾을 수 있습니다.
• 분할 정복: 배열을 분할하여 각 부분에서 다수의 요소를 찾고, 합치는 방식으로 접근할 수도 있습니다.

---

🔍 문제 풀어보기

1. Array Traversal with Hash Table 배열순회와 해시 테이블

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        # Using a dictionary to store the frequency of each element
        counts = {}
        for num in nums:
            if num not in counts:
                counts[num] = 1
            else:
                counts[num] += 1

            # If the frequency count of the current element is more than half the size of the array,
            # we have found our majority element
            if counts[num] > len(nums) // 2:
                return num

 

• 배열의 각 요소를 순회하며, Python의 dict를 사용하여 각 요소의 출현 횟수를 기록합니다.
• 배열의 절반 이상을 차지하는 요소를 찾으면 그 요소가 바로 다수의 요소가 됩니다.

2. Boyer-Moore Voting Algorithm

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

            count = 0
            candidate = None

            for num in nums:
                if count == 0:
                    candidate = num
                count += (1 if num == candidate else -1)
                print(candidate, count)

            return candidate

• 배열을 단 한 번만 순회하면서 현재 후보의 카운트를 조정합니다.
• 카운트가 0이 될 때마다 새로운 요소를 후보로 선택합니다.
• 배열의 끝에 도달했을 때 남은 후보가 다수의 요소가 됩니다.
• 이 방법은 시간 복잡도 O(n), 공간 복잡도 O(1)로 매우 효율적입니다.

 

 

---

"169. Majority Element" 문제를 해결하기 위한 다양한 접근법을 배웠습니다. 이러한 방법들을 통해 다른 코딩 문제에도 유사한 전략을 적용할 수 있을 것입니다. 코딩 인터뷰 준비에 있어서는 다양한 문제에 대해 유연하게 접근하는 능력이 중요합니다. 오늘 배운 내용을 바탕으로 여러분의 코딩 인터뷰 준비가 더욱 탄탄해지길 바랍니다! 💡🚀