Level
프로그래머스 Lv3
Day
18일
kakao
2020 카카오 블라인드
 
function solution(n, weak, dist) {
    let answer = 0;
    
    const getPermutation = (arr) => {
        if(arr.length===1) return [arr]
        
        const permutations = []
        
        const picked = arr[0]
        
        const smallerPermutations = getPermutation(arr.slice(1))
        for(let i=0; i<smallerPermutations.length; i++){
            const smallerPermutation = smallerPermutations[i]
            
            for(let cut=0; cut <= smallerPermutation.length; cut++){
                const prefix = smallerPermutation.slice(0, cut)
                const suffix = smallerPermutation.slice(cut)
                
                permutations.push(prefix.concat([picked], suffix))
            }
        }
        return permutations
    }
    
    const distPermutations = getPermutation(dist)
    
    
    const expandedWeak = [...weak, ...weak.map(w => w + n)]
    const rotatedWeaks = Array(weak.length).fill(0).map((w,i) => expandedWeak.slice(i, i+weak.length))
    
    const participate = (weak, participants) => {
        let start = 0
        let end = 0
        
        for(let i=0; i<participants.length; i++){
            const participant = participants[i]
            
            const destination = weak[start] + participant
            if(destination < weak[end]) return false
            while(destination >= weak[end]){
                end++
                if(end===weak.length) return i+1
            }
            start = end
        }
        
        return false;
    }
    
    
    let min = Infinity
    distPermutations.forEach(participants => {
        for(let i=0; i<rotatedWeaks.length; i++){
            const rotatedWeak = rotatedWeaks[i]
            const number = participate(rotatedWeak, participants)
            
            if(number){
                min = Math.min(min, number)
            }
        }
    })
    
    return min=== Infinity ? -1 : min;
}