파이썬으로 정렬된 배열에서 과반수(majority) 요소인지 확인하는 방법

오름차순(비내림차순)으로 정렬된 배열 nums와 하나의 숫자 target이 주어졌을 때, 이 타깃이 해당 배열의 과반수(majority) 요소인지 판별해야 합니다.

여기서 과반수 요소란 길이가 N인 배열에서 N/2번보다 많이 등장하는 요소를 의미합니다. 예를 들어 배열이 [2, 4, 5, 5, 5, 5, 5, 6, 6]이고 타깃이 5라면, 5는 총 5번 등장하므로 배열 길이 9의 절반인 4.5보다 큽니다. 따라서 결과는 true가 됩니다.

문제 해결 접근 방법

정렬된 배열의 특성을 활용하면 이진 탐색(binary search)으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 타깃 값이 처음 나타나는 위치와 마지막으로 나타나는 위치를 찾아 그 개수를 계산하는 것입니다.

이를 위해 두 개의 보조 함수를 사용합니다.

1. lower() 함수 — 첫 번째 등장 위치 찾기

배열 arr과 target 두 개의 인자를 받습니다.
low := 0, high := len(arr)로 초기화합니다.
low < high인 동안 반복합니다.
- mid := low + (high - low) // 2
- arr[mid] == target이면 high = mid, 아니면 low = mid + 1
arr[high] == target이면 high를 반환하고, 아니면 -1을 반환합니다.

2. upper() 함수 — 마지막 등장 위치 찾기

마찬가지로 배열 arr과 target을 인자로 받습니다.
low = 0, high = len(arr) - 1로 초기화합니다.
low < high인 동안 반복합니다.
- mid = low + (high - low + 1) // 2
- n[mid] == target이면 low = mid, 아니면 high = mid - 1
n[low] == target이면 low를 반환하고, 아니면 -1을 반환합니다.

3. 메인 로직

u := upper(arr, target) — 마지막 등장 위치
l := lower(arr, target) — 첫 번째 등장 위치
u != -1이고 (u - l + 1) > len(nums) / 2이면 true를 반환하고, 그렇지 않으면 false를 반환합니다.

두 위치의 차이에 1을 더하면 타깃의 총 등장 횟수가 되며, 이 값이 배열 길이의 절반보다 큰지 비교하면 됩니다.

파이썬 구현 예제

다음 코드를 통해 실제 구현 방법을 살펴보겠습니다.

class Solution(object):
    def upper(self, n, target):
        low = 0
        high = len(n) - 1
        while low < high:
            mid = low + (high - low + 1) // 2
            if n[mid] == target:
                low = mid
            else:
                high = mid - 1
        return low if n[low] == target else -1

    def lower(self, n, target):
        low = 0
        high = len(n) - 1
        while low < high:
            mid = low + (high - low) // 2
            if n[mid] == target:
                high = mid
            else:
                low = mid + 1
        return high if n[high] == target else -1

    def isMajorityElement(self, nums, target):
        u = self.upper(nums, target)
        l = self.lower(nums, target)
        return u - l + 1 > len(nums) / 2 if u != -1 else False

ob1 = Solution()
print(ob1.isMajorityElement([2, 4, 5, 5, 5, 5, 5, 6, 6], 5))

입력

[2, 4, 5, 5, 5, 5, 5, 6, 6]
5

출력

true

시간 복잡도 분석

이 알고리즘은 이진 탐색을 두 번 수행하므로 시간 복잡도는 O(log N)입니다. 배열을 한 번씩 순회하는 O(N) 방식보다 훨씬 효율적이며, 특히 배열이 이미 정렬되어 있다는 조건이 주어진 경우 최적의 선택입니다. 공간 복잡도 역시 추가 메모리를 사용하지 않으므로 O(1)입니다.