2780. Minimum Index of a Valid Split

문제

An element x of an integer array arr of length m is dominant if more than half the elements of arr have a value of x.

You are given a 0-indexed integer array nums of length n with one dominant element.

You can split nums at an index i into two arrays nums[0, ..., i] and nums[i + 1, ..., n - 1], but the split is only valid if:

0 <= i < n - 1
nums[0, ..., i], and nums[i + 1, ..., n - 1] have the same dominant element.
Here, nums[i, ..., j] denotes the subarray of nums starting at index i and ending at index j, both ends being inclusive. Particularly, if j < i then nums[i, ..., j] denotes an empty subarray.

Return the minimum index of a valid split. If no valid split exists, return -1.

문제

• 특정 배열의 길이의 절반을 초과하는 만큼 등장하는 수는 과반수 라고 부릅니다.
• [0~i] 와 [i+1~N] 의 범위로 배열을 나눴을때, 왼쪽과 오른쪽 배열의 과반수가 같아지는 가장 작은 i를 리턴하세요
• 다만 없으면 -1을 리턴하세요

---

예시

[1,2,2,2]

는

[1, 2, 2] 와 [2] 로 나뉠수 있다.

---

제한

• $1 <= nums.length <= 10^5$
• $1 <= nums[i] <= 10^9$
• nums는 반드시 하나의 과반수를 가진다.

---

풀이

• 왼쪽과 오른쪽의 Hashmap을 만든다.
• 갱신하면서 갱신된 값에 대해서만! 과반수가 되는지를 검사한다.

class Solution:
    def minimumIndex(self, nums: List[int]) -> int:
        N = len(nums)

        cntr = Counter(nums)

        left = defaultdict(int)
        right = cntr

        for i in range(N - 1):
            left_size = i + 1
            right_size = N - i - 1

            target = nums[i]
            left[target] += 1
            right[target] -= 1

            if left[target] > left_size // 2 and right[target] > right_size // 2:
                return i

        return -1

---

후기

• 너무 쉬운데... 왜 어렵게 생각했지