프로그래머스: 외벽 점검 - javascript(깔쌈한 구현 문제, 순열 활용)

문제 출처 

https://school.programmers.co.kr/learn/courses/30/lessons/60062

프로그래머스

 

문제 풀이 힌트 

정말 깔~쌈한 문제라고 생각한다. 

순열 구하는 함수를 안다면 바로 코드 작성하고, 

구현을 잘 ~ 하면 된다. 

 

시계방향이냐, 반시계 방향이냐? 를 고민하지 않게 만드는 건 

- 일렬로 배열을 더 길게 늘려주는 것이다. 

=> 뭐 예를 들어서 n이 12다? 그럼 0은 12라는 또 다른 숫자이기도 하다.

- 1은 13이라는 숫자이기도 하다. 

- 2는 14라는 숫자이기도 하다. 

즉, 저렇게 생각함으로써 10과 1(=13)의 거리 차이는 3이 된다. 

 

고려 해야 할 것은 ? 

1)  몇명을 투입하냐?

2)  어떤 사람의 조합으로 투입하냐? 

=> 이 두개는 순열 함수로 해결 가능 

3) 시작 지점은?

=> 반복문을 통해 weak 지점 각각을 시작 지점으로 설정한다. 

4)  해당 사람이 어디까지 커버리지 가능한가?

=> 시작 위치 + 그 사람의 이동 거리 

 

정답 풀이 코드 

function solution(n, weak, dist) {
    const len = weak.length; //취약한 지점 몇개?
    const linear_weak = new Array(len*2 -1).fill(0); //방향을 무력화 시키는 배열임. 각각의 숫자를 또 다른 숫자로 표현하기 위함.  
    
    for(let i=0; i<len*2-1; i++){ //위에 만든 배열에 해당하는 숫자를 적어준다. 
        linear_weak[i] = i < len ? weak[i] : weak[i-len] + n; /ex) n이 12일 때 0은 12라는 숫자도 됨. 1은 13
    }
    dist.sort((a,b) => b-a); //내림차순 정렬로 한다. 적은 사람 수 투입을 위해 이동거리 큰 애들 부터 투입 할 것임. 
    
    for(let i=1; i <= dist.length; i++){ //사람 수 몇명 투입? 
        const permutation = getPermutation(dist, i); //정한 사람수로 순서있는 조합 얻기 
        
        for(const permu of permutation){//해당 순열
            for(let j=0; j<len; j++){//시작지점을 ? 어디로 ?
                let line = linear_weak.slice(j, len+j); //시작지점을 변경한 새로운 배열 생성 
                for(const p of permu){//순열의 해당 사람이 어디까지 커버리지 가능한지? 
                    const coverage = line[0] + p; //시작 지점 + 자기 이동 거리 
                    line = line.filter(e => e > coverage); //해당 사람이 이동한 곳보다 큰 숫자 지점들만 아직 해결 못한 곳임. 
                    if(!line.length) return i; //더이상 해결 못한 지점이 없을 때 조건에 맞는 순열이였던 거고, 그때 사람 수 i를 return 한다. 
                }
            }
        }
    }
    return -1; 
}

const getPermutation = (arr, n) => {
    if(n ===1) return arr.map(v => [v]); 
    const result = []; 
    
    arr.forEach((fixed, idx, origin) => {
        const rest = [...origin.slice(0, idx), ...origin.slice(idx+1)]; 
        const perms = getPermutation(rest, n-1)
        const attached = perms.map((perm) => [fixed, ...perm]); 
        result.push(...attached)
    }); 
    return result; 
}

Only 풀이 코드 

function solution(n, weak, dist) {
    const len = weak.length; 
    const linear_weak = new Array(len*2 -1).fill(0); 
    
    for(let i=0; i<len*2-1; i++){
        linear_weak[i] = i < len ? weak[i] : weak[i-len] + n; 
    }
    dist.sort((a,b) => b-a); 
    
    for(let i=1; i <= dist.length; i++){ 
        const permutation = getPermutation(dist, i); 
        
        for(const permu of permutation){
            for(let j=0; j<len; j++){
                let line = linear_weak.slice(j, len+j); 
                for(const p of permu){
                    const coverage = line[0] + p; 
                    line = line.filter(e => e > coverage); 
                    if(!line.length) return i; 
                }
            }
        }
    }
    return -1; 
}

const getPermutation = (arr, n) => {
    if(n ===1) return arr.map(v => [v]); 
    const result = []; 
    
    arr.forEach((fixed, idx, origin) => {
        const rest = [...origin.slice(0, idx), ...origin.slice(idx+1)]; 
        const perms = getPermutation(rest, n-1)
        const attached = perms.map((perm) => [fixed, ...perm]); 
        result.push(...attached)
    }); 
    return result; 
}