프로그래머스 - 외벽 점검

1. 문제 링크

문제 링크

2. 풀이

전형적인 브루트포스 유형의 문제입니다.
차근차근 풀어보겠습니다.

1. 친구들을 투입하는 모든 경우의 수 만들기

친구들을 어떤 순서로 투입하느냐에 따라 1명만 투입할 수도, 전부 다 투입해야 할 수 있습니다.
그러므로 친구들의 투입 순열을 만들어줍니다.

// 친구 투입 순열 만들기
(function f(depth, make, used) {
    if (depth == dist.length) {
        friendPermutation.push([...make]);
        return;
    }

    for (let i = 0; i < dist.length; i++) {
        if (used[i]) continue;

        used[i] = 1;
        make.push(dist[i]);
        f(depth + 1, make, used);
        make.pop();
        used[i] = 0;
    }
})(0, [], [...Array(dist.length)].map(() => 0));

결론적으론 friendPermutation 배열에 순열이 모두 담기게 됩니다.

2. [0, n-1] 구간에 친구들을 투입하기

for (let i = 0; i < n; i++) {
    for (const friends of friendPermutation) {
        ans = Math.min(ans, inject(i, friends));
    }
}

1에서 만든 친구 순열을 투입할 수 있는 곳에서 다 투입해보면 됩니다.
투입해서 가장 적은 친구수로 커버칠 수 있는 수가 정답이 됩니다.

// 취약 지점 2n으로 늘리고
const weaks = [...Array(weakSize * 2)].map(() => 0);

// 취약 지점 늘린만큼 다시 세팅
weak.sort((a, b) => a - b).forEach((v, i) => {
    weaks[i] = v;
    weaks[i + weakSize] = v + n;
});

// 친구 투입
const inject = (s, friends) => {
    for (let i = 0, p = 0; i < friends.length; i++) {
        const a = weaks[s + p];
        
        // 현재 친구가 커버칠 수 있는 만큼 p를 증가
        while (p < weakSize && weaks[s + p] - a <= friends[i]) {
            p++;
        }
        // p가 전 구간을 다 돌았으면 친구수 리턴
        if (p == weakSize) return i + 1;
    }

    return INF;
};

친구를 투입하는 로직은 간단합니다.
일단 레스토랑이 원형이기 때문에 로직을 구현하기 편하도록 2n으로 늘려주고
현재 친구가 커버칠 수 있을 때까지 취약 지점을 순회하면 됩니다.

3. 전체 코드

function solution(n, weak, dist) {
    const INF = 987654321;
    const weakSize = weak.length;
    const weaks = [...Array(weakSize * 2)].map(() => 0);
    const friendPermutation = [];

    // 친구 투입 순열 만들기
    (function f(depth, make, used) {
        if (depth == dist.length) {
            friendPermutation.push([...make]);
            return;
        }

        for (let i = 0; i < dist.length; i++) {
            if (used[i]) continue;

            used[i] = 1;
            make.push(dist[i]);
            f(depth + 1, make, used);
            make.pop();
            used[i] = 0;
        }
    })(0, [], [...Array(dist.length)].map(() => 0));
    
    weak.sort((a, b) => a - b).forEach((v, i) => {
        weaks[i] = v;
        weaks[i + weakSize] = v + n;
    });

    let ans = INF;

    const inject = (s, friends) => {
        for (let i = 0, p = 0; i < friends.length; i++) {
            const a = weaks[s + p];
            
            while (p < weakSize && weaks[s + p] - a <= friends[i]) {
                p++;
            }

            if (p == weakSize) return i + 1;
        }

        return INF;
    };
    
    for (let i = 0; i < n; i++) {
        for (const friends of friendPermutation) {
            ans = Math.min(ans, inject(i, friends));
        }
    }

    return ans == INF ? -1 : ans;
}