[programmers] 외벽 점검 (in JS)

문제

외벽점검 - 2020 카카오 블라인드 채용

Fact

• 어떠한 순서로 친구들을 보냈을 때, 전부 점검할 수 있는지 알기 위해서, 친구들의 모든 순열을 구해야 한다.

• 가장 적은 친구가 필요한 경우를 찾아야 하므로, 친구들의 순열은 그 길이가 1인 것부터 확인해야 한다.

• 친구들이 점검할 때, 어떠한 weak부터 시작하느냐에 따라 전부 점검할 수 있을 수도 있고, 아닐 수도 있다. 그러므로, 모든 weak를 시작점으로 설정하여 점검해봐야 한다.

• 외벽은 원형이기 때문에, 배열의 시작점부터 어떠한 거리를 더하였을 때, 그 인덱스가 배열을 벗어날 수 있기 때문에, 인덱스가 배열 안으로 들어오도록 조정해야 한다.

  next_index = (current_index + distance) mod (array_length)

접근

• 친구들에 대해 가능한 모든 순열을 구한다.

• 각 순열에 대해서 다음을 반복한다.

  • weak의 모든 지점을 시작점으로 하여, 아래를 반복한다. 그 중 한 순열이라도, 모든 취약점을 점검할 수 있다면, 그 순열의 길이를 반환한다.
  • 친구들이 찾을 weak의 시작점이 weak배열의 첫 번째 요소로 오도록 수정한다.

  const unFoundWeak = [...weak.slice(startIdx), ...weak.slice(0, startIdx)];

  • dist 순열의 각 element 별로, weak의 첫 번째 인덱스부터 몇 개의 weak을 찾을 수 있는지 찾아서 더한다. 이 때, 찾은 weak은 배열에서 제거한다.
  • 이전에 구한 값이, 모든 취약점의 갯수와 같다면, 그 순열의 크기를 반환한다.

• 모든 순열에 대해서 취약점을 전부 찾을 수 없다면, -1을 반환한다.

코드

const findNextLoc = (cur, next, n) => (cur + next) % n;

const permutation = (arr, k, list, result) => {
  if (list.length === k) {
    result.push(list);
    return;
  }
  for (let i = 0; i < arr.length; i++) {
    const nextArr = [...arr.slice(0, i), ...arr.slice(i + 1)];
    permutation(nextArr, k, [...list, arr[i]], result);
  }
  return result;
};
const countWeak = (unFoundWeak, distance, n) => {
  let count = 0;
  const start = unFoundWeak[0];
  for (let next = 0; next <= distance; next++) {
    const nextLoc = findNextLoc(start, next, n);
    if (nextLoc !== unFoundWeak[0]) {
      continue;
    }
    count += 1;
    unFoundWeak.shift();
  }
  return count;
};

function solution(n, weak, dist) {
  const totalWeak = weak.length;
  for (let k = 1; k <= dist.length; k++) {
    const combiList = permutation(dist, k, [], []);
    const findAll = combiList.some((list) => {
      for (let startIdx = 0; startIdx < weak.length; startIdx++) {
        const unFoundWeak = [
          ...weak.slice(startIdx),
          ...weak.slice(0, startIdx),
        ];
        const foundCount = list.reduce((sum, distance) => {
          const count = countWeak(unFoundWeak, distance, n);
          return sum + count;
        }, 0);
        if (foundCount === totalWeak) {
          return true;
        }
      }
      return false;
    });
    if (findAll) {
      return k;
    }
  }
  return -1;
}

소감

홍신 교수님께서는 PS할 때, 함수 이름, 변수명 등 자세하게 손으로 써보고, 코드를 쓰는 것은 가장 적게 하라고 하셨다. 이게 처음 문제를 보고서는 실천하게 되는데, 코드에 문제가 있을 때 디버그할 때는 디버거를 통해 문제를 파악하게 된다. 이렇게하면 디버거를 안썼을 때보다는 잘 보이겠지만, 에러를 찾는데 너무 오래 걸린다. 이 문제도, 이렇게 고치면 정답이 얻어걸리지 않을까 하는 생각으로 디버깅을 했었던 것 같다. 어림도 없지 ㅋ 코드를 짤 때는 논리적으로 생각하고, 검토를 거쳐서 짜야할 것 같다.
최대한 종이에 많이 써보고, 틀린 점은 예제는 어떤게 있을지 생각해보고 코드를 짜는 연습이 필요한 것 같다.