๐Ÿ”’Algorithm

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

devWarrior 2025. 4. 5. 17:14

๋ฌธ์ œ๋งํฌ

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

}