프로그래머스 [Lv. 3] 외벽 점검 {언어 : JavaScript} [다시 풀어 보기]

문제 링크

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

프로그래머스

정답 코드

function solution(n, weak, dist) {
    const lenD = dist.length;
    const lenW = weak.length;
    let answer = lenD + 1;  // 최악의 경우 lenD 이상의 값으로 초기화
    
    // 모든 친구의 순열 생성
    function generatePermutations(arr) {
        if (arr.length === 1) return [arr];
        const permutations = [];
        for (let i = 0; i < arr.length; i++) {
            const rest = [...arr.slice(0, i), ...arr.slice(i + 1)];
            const restPermutations = generatePermutations(rest);
            for (const perm of restPermutations) {
                permutations.push([arr[i], ...perm]);
            }
        }
        return permutations;
    }

    const permutations = generatePermutations(dist);

    // 약점을 원형으로 처리하기 위해 두 배로 확장
    for (let i = 0; i < lenW; i++) {
        weak.push(weak[i] + n);
    }

    // 각 시작점에서 모든 순열에 대해 검사
    for (let start = 0; start < lenW; start++) {
        for (const perm of permutations) {
            let count = 1; // 첫 번째 친구부터 사용
            let position = weak[start] + perm[count - 1];

            for (let index = start; index < start + lenW; index++) {
                if (position < weak[index]) {
                    count++;
                    if (count > lenD) break;
                    position = weak[index] + perm[count - 1];
                }
            }
            if (count < answer) {
                answer = count;
            }
        }
    }

    if (answer > lenD) {
        answer = -1;
    }
    return answer;
}

풀이 방법

 

1. 모든 친구의 배치 경우의 수 계산 (순열 생성):
   • generatePermutations 함수를 사용하여 모든 친구들의 가능한 배치를 순열로 생성한다.
   • 이 순열들은 친구들이 벽을 검사하는 순서를 나타낸다.
2. 원형 벽을 직선으로 펼치기:
   • 원형 벽의 약점을 검사할 때 원형으로 돌아가야 하므로, 이를 처리하기 위해 약점 배열을 두 배로 확장한다. 이렇게 하면 원형으로 돌아가는 것을 직선처럼 처리할 수 있다.
   • 예를 들어, 약점이 [1, 5, 6, 10] 이라면 [1, 5, 6, 10, 1+n, 5+n, 6+n, 10+n] 와 같이 확장한다.
3. 각 시작점에서 모든 순열에 대해 검사:
   • 약점 배열의 각 위치를 시작점으로 두고 모든 순열을 검사한다.
   • 특정 순열을 사용하여 각 친구가 검사할 수 있는 범위를 계산합니다. 이때, 친구가 검사할 수 있는 범위 내에 있는 모든 약점을 처리한다.
   • 친구가 처리할 수 없는 범위에 새로운 약점이 나타나면 다음 친구를 사용한다.
4. 최소 인원 계산:
   • 각 순열에 대해 필요한 친구들의 수를 계산하고, 이를 최소 인원으로 업데이트한다.
   • 모든 가능한 경우를 다 검사한 후, 최소 인원을 반환한다. 만약 필요한 친구들의 수가 주어진 친구들의 수보다 많으면 -1로 치환한다.

 

느낀점

• 순열을 만드는 것에는 문제가 없었지만 최소 인원을 계산하는 방식에서 어려움이 있었다.