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
}