LeetCode [JS] > 2780. Minimum Index of a Valid Split

문제링크

https://leetcode.com/problems/minimum-index-of-a-valid-split/description/

문제풀이

dominant한 수는 주어진 배열에서 정확히 1개라고 전제가 되어 있다. 배열에서 특정 수가 반보다 많이 등장한다는 애기이다. 예를들어서 [1,2,3,2] 이런 배열은 dominant수가 없기 때문에 주어질 수 없다는 애기이다. 

 

주어진 배열을 split 하여 왼쪽, 오른쪽 2개의 배열로 나누었을 때 각 배열의 dominant한 수가 같은 split point를 알아야 된다.

주어진 배열에서 dominant한 수는 한개이므로  애초에 주어진 배열을 2개로 나누고 각 배열의 dominant한 수가 같을 때 그 수는 원래 배열의 dominant 수일 수 밖에 없다.

 

위 사실을 알면 우리는 전체배열의 dominant한 수를 구한 뒤 주어진 배열을 순서대로 순회하면서 왼쪽,오른쪽 배열의 dominant 수의 갯수만 파악하면 유효한 split point를 알 수 있다.

 

이 문제의 시간 복잡도는 O(n)으로 파악된다.

/**
 * @param {number[]} nums
 * @return {number}
 */
var minimumIndex = function(nums) {

  const l = nums.length

  // Step 1: 전체 카운트 맵 만들기
  const totalMap = new Map()
  for(const n of nums){
    totalMap.set(n,(totalMap.get(n)||0)+1)
  }

  // Step 2: dominant element 찾기 (조건: 등장 횟수가 절반 초과)
  let dominant = -1
  for(const [n,cnt] of totalMap.entries()){
        if(cnt*2>l){
            dominant = n
            break;
        }
  }
    
  let splitIdx = undefined
  let leftCnt = 0
  let rightCnt = totalMap.get(dominant)

  // Step 3: 왼쪽 카운트 누적하면서 valid split 찾기
  for(let i=0; i<=l-1; ++i){
    
    if(nums[i]===dominant){
        ++leftCnt 
        --rightCnt
    }
    
    if(leftCnt*2>i+1&&rightCnt*2>l-(i+1)){
        splitIdx = i
        break
    }    
  }

  return splitIdx === undefined ? -1 : splitIdx

}