[JS] 외벽 점검

문제

프로그래머스

 

풀이

이번 문제는 원형 탐색과 순열을 이용해 풀이를 진행했다.

 

중요한 것은 로직의 구성인거 같다.

1. 몇 명을 선택할 것인가?
2. 정해진 인원을 누구로 채울것인가?
3. 어디 부터 시작할 것인가?
4. 각 인원이 어디까지 커버할 수 있는가?

위의 네 가지 로직을 구현한다면 문제없이 문제 풀이가 가능할 것이다.

코드

function solution(n, weak, dist) {
  const getPermutation = (arr, n) => {
    if (n === 1) return arr.map((e) => [e]);
    let res = [];

    for (let i = 0; i < arr.length; i++) {
      const rest = [...arr.slice(0, i), ...arr.slice(i + 1)];
      const perm = getPermutation(rest, n - 1);
      const permArr = perm.map((e) => [arr[i], ...e]);
      res.push(...permArr);
    }
    return res;
  };

  let arr = Array.from(
    { length: weak.length * 2 },
    (_, i) => weak[i % weak.length] + (i >= weak.length ? n : 0)
  );
  dist.sort((a, b) => b - a);

  //     for(let i = 1; i <= dist.length; i++){
  //         const permutation = getPermutation(dist, i);

  //         for(let j = 0; j < weak.length; j++){
  //             for(let perm of permutation){
  //                 let range = arr.slice(j, j + weak.length);
  //                 for(let p of perm){
  //                     range = range.filter(e => e > range[0] + p);
  //                     if(range.length === 0) return i;
  //                 }
  //             }
  //         }
  //     }

  for (let i = 1; i <= dist.length; i++) {
    const permutation = getPermutation(dist, i);

    for (let perm of permutation) {
      for (let j = 0; j < weak.length; j++) {
        let end = arr.slice(j, j + weak.length);
        for (let p of perm) {
          end = end.filter((e) => e > end[0] + p);
          if (end.length === 0) return i;
        }
      }
    }
  }
  return -1;
}