programmers. 외벽 점검

문제

문제

코딩테스트 연습 - 외벽 점검

풀이

완전 탐색은 아직도 감이 잘 안잡힌다.. 더 많이 풀어봐야지

친구 수가 최대 8명이기 때문에 친구들의 점검 거리값으로 순열을 구해서 저장한 뒤

        [1,2,3,4],
        [1,2,4,3],
        [1,3,2,4],
        [1,3,4,2],
        [1,4,3,2]
        ...

구한 순열을 모두로 외벽을 점검해본다 이 때 외벽을 [1, 5, 6, 10] 차례대로 점검을 보낼 수도 있지만

[5, 6, 10, 1] 순서로도 보낼 수 있다 이 경우에는 벽이 원으로 둘러 쌓여있다는 점을 이용해서 [5, 6, 10, 13] 로도 표현이 가능하다 (shift->push)

코드

    function patrol(people, weakCopy) {
        const peopleC= [...people];
        const weakC = [...weakCopy];
        while (peopleC.length) {
            const pTemp = peopleC.shift();
            const wTemp = weakC.shift();

            while (weakC[0] <= (pTemp + wTemp)) {
                weakC.shift();
            }
        }
        return weakC.length;
    }


    function solution(n, weak, dist) {
        var answer = -1;
        const arr = [];

        for(let i=1; i<=dist.length;i++){
            arr.push(...getP(dist,i));
        }

        for(let i= 0;i<arr.length;i++){
            const people = [...arr[i]];
            const weakCopy = [...weak];
            const len = people.length;
            for(let i=0; i<weakCopy.length;i++){
                weakCopy.push(weakCopy.shift()+n);
                if(!patrol(people,weakCopy)) return len;
            }
        }
        return answer;
    }


    function getP(arr,len){
        const result = [];
        if(len===1) return arr.map(v=>[v]);

        arr.forEach((v,i)=>{
            const fixed = v;
            const rest = arr.filter((v,idx)=>i!==idx);
            const temp = getP(rest,len-1);
            const merge = temp.map(v=>[fixed,...v]);
            result.push(...merge);
        });

        return result;
    }