Minimum Index of a Valid Split

문제 설명

• 길이가 n인 정수 배열 nums가 주어집니다.
  • 이 배열에는 하나의 dominant elment가 존재합니다.
  • dominant element란, 배열의 전체에서 절반 이상을 차지하는 숫자를 의미합니다.
• 배열을 인덱스 i에서 두 개의 부분 배열로 분할할 수 있습니다.
  • nums[0, …, i]: 왼쪽 부분 배열
  • nums[i + 1, …, n - 1]: 오른쪽 부분 배열
• 이때, 두 부분 배열이 같은 dominant element를 가지도록 분할할 수 있는, 가장 작은 인덱스 i를 반환해야 합니다.
  • 만약 유효한 분할이 불가능하다면 -1을 반환합니다.

문제 풀이

Hash Table

Map을 사용하여, 배열의 숫자의 개수를 추적하여 문제를 해결할 수 있습니다.

1. 전체 숫자의 등장 횟수를 저장: totalCounter
2. 왼쪽 부분 배열에서 숫자의 등장 횟수를 저장: counter
3. 각 인덱스 i에서 분할 가능 여부를 확인
   • leftCount: nums[i]가 왼쪽 배열에서 등장한 횟수로 counter.get(nums[i]) + 1
   • rightCount: nums[i]가 오른쪽 부분 배열에서 등장한 횟수로 totalCount - leftCount
   • dominant element의 조건을 만족하는지 확인
     • 2 * leftCount > i + 1 → 왼쪽 배열에서 dominant element가 맞는지 확인
     • 2 * rightCount > n - i - 1 → 오른쪽 배열에서도 dominant element가 맞는지 확인
     • 위 조건을 만족하는 첫번째 i를 반환
4. 조건을 만족하는 i가 없으면 -1을 반환

function minimumIndex(nums: number[]): number {
  const n = nums.length;
  const totalCounter = new Map<number, number>();
  for (const num of nums) {
    totalCounter.set(num, (totalCounter.get(num) ?? 0) + 1);
  }
 
  const counter = new Map<number, number>();
  for (let i = 0; i < n; i++) {
    const num = nums[i];
    const totalCount = totalCounter.get(num) ?? 0;
 
    const leftCount = (counter.get(num) ?? 0) + 1;
    const rightCount = totalCount - leftCount;
    counter.set(num, leftCount);
    if (2 * leftCount > i + 1 && 2 * rightCount > n - i - 1) {
      return i;
    }
  }
  return -1;
}

복잡도

• 시간 복잡도: $O(n)$
• 공간 복잡도: $O(n)$

Boyer-Moore Majority Vote

주어진 배열 nums에는 하나의 dominant element가 존재하므로, Boyer-Moore Majority Vote 알고리즘을 활용해 과반수를 차지하는 요소를 효율적으로 찾습니다. 이후, 해당 요소의 개수를 추적하여 추가적인 Map을 사용하지 않고도 문제를 해결할 수 있습니다.

1. 배열에서 dominant element 찾기(Boyer-Moore Majority Vote): findDominantElement()
   • 주어진 배열 nums에서 과반수를 차지하는 dominant element가 반드시 존재하므로, Boyer-Moore Majority Vote 알고리즘을 사용하여 dominant element를 찾음.
2. dominant element의 총 개수를 계산: totalCount
3. 최소 분할 인덱스 찾기
   • leftCount: 왼쪽 부분 배열에서 dominant element의 등장 횟수를 계산
   • rightCount: 오른쪽 부분 배열에서 남은 개수, totalCount - leftCount
   • dominant element의 조건을 만족하는지 확인
     • 2 * leftCount > i + 1 → 왼쪽 배열에서 dominant element가 맞는지 확인
     • 2 * rightCount > n - i - 1 → 오른쪽 배열에서도 dominant element가 맞는지 확인
     • 위 조건을 만족하는 첫번째 i를 반환
4. 조건을 만족하는 i가 없으면 -1을 반환

export function minimumIndex(nums: number[]): number {
  const n = nums.length;
  const dominantElement = findDominantElement(nums);
  const totalCount = nums.reduce((count, num) => (num === dominantElement ? count + 1 : count), 0);
 
  let leftCount = 0;
  for (let i = 0; i < n; i++) {
    if (nums[i] === dominantElement) {
      leftCount += 1;
    }
 
    const rightCount = totalCount - leftCount;
    if (2 * leftCount > i + 1 && 2 * rightCount > n - i - 1) {
      return i;
    }
  }
  return -1;
}
 
function findDominantElement(nums: number[]): number {
  let count = 0;
  let candidate = 0;
  for (const num of nums) {
    if (count === 0) {
      candidate = num;
    }
    count += candidate === num ? 1 : -1;
  }
  return candidate;
}

복잡도

• 시간 복잡도: $O(n)$
• 공간 복잡도: $O(1)$