문제 링크

프로그래머스 문제

풀이

완전탐색으로 풀려고 했으나, 그럼에도 불구하고 시간초과가 발생하여
다른분의 풀이를 참고하게 되었다.

쉽게 이해가 가능하도록 설명해 주셔서 어렵지 않게 응용할 수 있었다.
중요한 포인트는 두가지인데
linerWeak라는 배열에다가 2배의 길이로 weak를 만들어주는것이다.
이를 통해서 방향을 고려하지 않아도 되는 하나의 배열을 만들어준다.
두번째는 순열이다. 서로다른 속도를 가진 직원들을 순열을 통해서 모두 가용해 주어야 한다.

코드

function solution (n, weak, dist) {
  const weakLen = weak.length;
  const linearWeak = new Array(weakLen*2).fill(0); // 두배 만큼 만든다. 
  
  for(let i = 0; i < weakLen*2; i++){
      if(i < weakLen ){
          linearWeak[i] = weak[i]
      }else{ // 두배를 넘는 지점 부터는 원래의 값을 추가해준다. 
          linearWeak[i] =n+ weak[i-weakLen]  
      }
  }
    
  // 1 3 4 9 10 13 15 16 ... 처럼 말이다. 사실 각 수의 차이가 중요하다.
  dist.sort((a, b) => b-a); // 내림차순 정렬
  
  for(let i = 1; i <= dist.length; i++) { // 길이가 1 부터 dist.length 만큼의
    const permutation = getPermutation(dist, i); // 순열을 반환한다. 
    
    for(const permu of permutation) { // 순열이 된 배열의 집합
        // permu는 순열의 집합 중 하나를 의미 [3,4] 혹은 [4,3]
      for(let j = 0; j < weakLen; j++) {
        let line = linearWeak.slice(j, weakLen+j); // 현 위치부터 사용할 line입니다. 
        for(const p of permu) {
          line = line.filter(e => e > line[0] + p); // line의 일정부분보다 큰지
          if(!line.length) return i;
        }
      }
    }
  }
  
  return -1;
}

const getPermutation = (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 = getPermutation(rest, n-1);
    const attached = perms.map(perm => [fixed, ...perm]);
    result.push(...attached);
  });
  
  return result;
}
    

// 외벽의 둘레는 n
// 점검시간은 1시간
// 친구들마다 1시간동안 이동할 수 있는 거리는 제각각
// 최소한의 친구들을 투입해 취약지점을 점검하고 나머지는 내부공사
// 친구들은 시계 혹은 반시계방향으로만 이동합니다.
// 1시간동안 점검을 위한 최소값