프로그래머스 LEVEL 3(외벽 점검)

사용 언어 : javascript
해결 날짜 : 2023-05-12
해결 방법 :
- 계산의 용이성을 위해
  - dist를 내림차순 정렬
  - circular 형태의 weak을 linear 형태로 변환
- 투입하는 친구의 수(i)를 1부터 dist 길이까지 늘려가며
  - dist 중 i개의 원소로 구성된 permutation 계산
    - permutation을 돌며
      - 초기 weak의 모든 원소로부터 시작하는 slice된 배열을
        
        ex) [ 1, 3, 4, 9, 10 ], [ 3, 4, 9, 10, 13 ], [ 4, 9, 10, 13, 15 ], [ 9, 10, 13, 15, 16 ]
      - 현재 permutation 원소들로 취약 지점을 모두 점검할 수 있을 때 i 반환
회고 :
- 처음에 circular 형태의 weak을 linear 형태로 변환하는 것, weak의 모든 원소에 대해 시작점으로 설정하는 것까지 생각해서 문제를 풀었으나
- weak의 모든 원소에 대해 시작점으로 설정한 값중 어느 것이 최적의 값인지 결정하는 방법을 생각하는 것이 오래 걸렸다…

코드

const getPermutations = (arr, n) => {
  if (n === 1) return arr.map((el) => [el]);
  const result = [];

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

  return result;
};

function solution(n, weak, dist) {
  const length = weak.length;

  dist.sort((a, b) => b - a);
  weak.forEach((w, i) => i !== length && weak.push(w + n));

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

    for (const permutation of permutations) {
      for (let j = 0; j < length; j++) {
        let temp = weak.slice(j, length + j);

        for (const p of permutation) {
          temp = temp.filter((t) => t > temp[0] + p);

          if (temp.length === 0) {
            return i;
          }
        }
      }
    }
  }

  return -1;
}

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges