[CodeKata] 프로그래머스: 11.14(일), 외벽 점검

🥋 Oooth More!! (Level 3) 

 

🧮 풀이

weak 배열을 2바퀴로 돌려서 생각하는 방법까진 접근했으나, 구체적인 풀이를 모범답안을 통해 공부했다.

 

🖇 리뷰

function solution (n, weak, dist) {
  const len = weak.length;
  const linear_weak = new Array(len*2 - 1).fill(0);
  
  for(let i = 0; i < len*2-1; i++)
    linear_weak[i] = i < len ? weak[i] : weak[i-len] + n;
  
  dist.sort((a, b) => b-a);
  
  for(let i = 1; i <= dist.length; i++) {
    const permutation = getPermutation(dist, i);
    
    for(const permu of permutation) {
      for(let j = 0; j < len; j++) {
        let line = linear_weak.slice(j, len+j);
        for(const p of permu) {
          const coverage = line[0] + p;
          line = line.filter(e => e > coverage);
          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;
}

* 출처 : https://velog.io/@longroadhome/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-LV.3-%EC%99%B8%EB%B2%BD%EC%A0%90%EA%B2%80-JS

 

1. getPermutation() 함수 : 최소투입인원 순열 반환

• 이 함수는, 인자로 arr(dist 목록), n(몇 명) 2개를 받는다. dist 친구들 중, n명을 사용하는 모든 순열을 반환하는 함수이다.
• n이 1이라면 각 친구들이 담긴 배열을, 2 이상이면 모든 순열의 경우의 수를 담은 배열을 2중배열 형태로 반환해준다.

 

2. solution() 풀이

• len은 weak의 길이이며, dist는 한번에 갈 수 있는 거리가 긴 친구부터 체크하는게 용이하므로 sort()로 내림차순을 적용한다.
• linear_weak는 반시계까지 계산할 수 있도록, 1부터 n 사이에 있는 요소들을 e와 e+n 두바퀴로 재구성한 배열이다. (가령, case1의 [1, 5, 6, 10] 은, n이 12이므로 [1, 5, 6, 10, 13, 17, 18] 이 된다. 마지막 요소는 시계방향 2바퀴가 반복되므로 e+n 추가시 제외)
  • 첫 반복문은, dist 친구들의 최소인원 수를 순회한다. 최초 1명에서, 최대 dist.length(전체) 명만큼 순회하며, 해당 인원의 친구 조합목록인 permutation을 getPermutation() 함수로 계산한다.
  • 두 번째 반복문은, permutation의 모든 케이스(permu)를 순회한다.
  • 세 번째 반복문은, linear_weak의 모든 회전경우를 계산하는 함수이다. 0번째부터 마지막인 len번째까지, 원래길이인 len만큼 잘라준다.
  • 네 번째 반복문은, permu의 각 친구가 갈 수 있는 거리(p)를 계산한다. coverage는 시작점(line[0])부터 p만큼 갈 수 있는 거리값으로, line은 이 coverage가 갈 수 있는 범위외로 filter() 된다.
  • 만약, 여기서 line이 남는다면 다음 p의 경우를 계산하고, 없다면 모든 weak을 커버한 것으로 dist 친구명수인 i를 정답으로 반환한다.
• line이 계속 남아있어 i를 반환하지 못했다면, 결국 불가한 경우로 이 땐 -1을 반환하면 된다.