[프로그래머스] 외벽 점검 - 자바스크립트

문제

 

코딩테스트 연습 - 외벽 점검

 

오랜만에 알고리즘 문제 포스팅이다.

 

우리의 목적은 코드이므로, 빠르게 코드부터 살펴보자.

---

코드

function solution(n, weak, dist) {
  const flattenWeak = [...weak, ...weak.map((elem) => elem + n)];
  const weakLen = weak.length;
  const distLen = dist.length;
  const visits = new Array(distLen).fill(0);
  let answer = distLen + 1;

  if (weakLen === 1) return 1;

  function permutation(L, arr) {
    if (L === distLen) {
      for (let i = 0; i < weakLen; i++) {
        const end = i + weakLen;
        let left = i;
        let cnt = 0;

        for (let elem of arr) {
          if (left >= end) break;
          cnt += 1;
          const maxDist = elem + flattenWeak[left];

          while (left < end && maxDist >= flattenWeak[left]) {
            left++;
          }
        }

        if (left < end) continue;

        answer = Math.min(answer, cnt);
      }
      return;
    }

    for (let i = 0; i < distLen; i++) {
      if (visits[i]) continue;
      visits[i] = 1;
      permutation(L + 1, [...arr, dist[i]]);
      visits[i] = 0;
    }
  }

  permutation(0, []);

  return answer === distLen + 1 ? -1 : answer;
}

---

풀이

문제가 꽤 길지만, 차근차근 조건을 보자.

 

기본적으로 숫자 n, 공사가 필요한 외벽의 배열 weak, 친구들의 이동가능거리 배열 dist 가 주어진다.

레스토랑은 원형이며, 둘레가 n이다.

친구들은 공사가 필요한 어떤 위치에서든, 점검을 시작할 수 있다.
자신의 점검 시작위치를 기준으로 친구는 외벽의 시계 혹은 반시계 방향으로 이동할 수 있다.

 

우리는, 모든 공사를 점검할 수 있는 가장 적은 친구의 수를 구하면 된다.

 

제한 조건)

• 1 <= n <= 20
• 1 <= weak.length <= 15
  • 외벽의 위치는 모두 다르다.
  • 외벽 weak는 오름차순으로 주어진다.
  • 외벽 weak의 원소는 0 ~ n-1의 정수다.
• 1 <= dist.length <= 8
  • 친구의 이동거리 dist의 원소는 1 ~ 100의 자연수다.

 

우선 다음과 같은 원형 레스토랑의 둘레는 n이다.
북쪽이 0이고 둘레는 n이므로 북쪽의 시계방향에는 1, 반시계방향에는 n-1이 위치할 것이다.

 

 

이동방향 통일시키기

친구가 이동하는 경로는 반시계, 시계 모두 가능한게 우선 문제다.
이 방향을 다 고려하면, 한도끝도없이 어려워지므로 시계방향으로 통일해보자.

그러기 위해서는 위의 그림에서 10 -> 1로 이동의 흐름을 쉽게 만들어야 한다.

 

현재 weak 배열 원소에 둘레에 해당하는 n씩을 더해서 weak 배열에 추가해보자.

기존 배열 [1, 5, 6, 10]이 [1, 5, 6, 10, 13, 17, 18, 22] 가 되고, 이제 친구는 시계방향으로만 이동해도 괜찮다.

이제 현재 따져봐야 할 이동 시작점은, 1 5 6 10에서 시작하는 경우이다.
왜냐하면 13에서부터 시작하면 [1, 5, 6, 10]과 다를 바 없으므로 10까지만 평가하면 된다.

 

그렇다면, 이제 친구들을 배치시켜봐야 한다.

 

 

친구 배치시키기

친구의 순서를 배치할 때는 순열을 이용해야 한다.

왜 순열을 이용할까? 그냥 배치하면 안되나?

예를 들어서, [1, 5, 6, 10] 점검을 친구 배열 [1, 3]에게 맡긴다면 어떻게 될까?

• 1의 이동거리의 친구가 5,6을 점검하고 3의 이동거리인 친구가 10,1을 점검한다면 점검을 완료할 수 있다.
• 그러나 1의 이동거리인 친구가 5,6을 점검하지 않고 10이나 1을 점검한다면 점검을 완료할 수 없다.

 

그러므로 [1,2,3] 의 배열의 경우 [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] 모두 순회해봐야겠다.

 

순열이라니 시간복잡도가 좀 걱정되지만, dist의 크기는 최대 8이므로 8P8 = 40,320회로 그래도 할만하다.

 

배치된 dist 배열들을 기반으로 이동을 수행하기

최소 친구의 수를 구해야 하므로, 완전 탐색이 필요하다.

 

순열에서 친구 순서의 배치가 끝났을 때 마다, 친구를 외벽에 배치시킨다.
이 때 첫번째 외벽, 두번째 외벽, 세번째 외벽 ... 마지막 외벽에서 시작할 때를 모두 검증해준다.

 

여기서 점검 성공과 점검 실패를 나눠야한다.

 

점검 성공

1. 모든 친구가 투입되기 이전에 모든 외벽을 점검했다.
2. 맨 마지막 친구가 투입될 때 모든 외벽을 점검했다.

점검 실패

1. 모든 친구가 투입되었으나 모든 외벽을 점검할 수 없었다.

우리는 점검 실패의 경우를 제외하고 친구가 투입된 숫자 중 최솟값을 구하면 된다.

 

이 검증을 모든 순열의 경우에 반복해주면 최솟값을 찾을 수 있다.
만약 정답이 초기값을 유지하고 있다면, 모든 경우가 점검 실패이므로 -1을 반환하면 된다.

 

장황하게 설명해서 이해가 잘 되는지 잘 모르겠지만, 코드에 주석을 달아 간단하게 설명하고 끝내겠다.

---

주석을 포함한 코드

function solution(n, weak, dist) {
  // 외벽의 시작과 끝부분을 이어붙이기 위해 flattenWeak를 선언했다.
  const flattenWeak = [...weak, ...weak.map((elem) => elem + n)];
  const weakLen = weak.length;
  const distLen = dist.length;
  // 방문 배열을 통해 순열을 만든다.
  const visits = new Array(distLen).fill(0);
  let answer = distLen + 1;

  // 외벽 원소가 1개면, 아무나 1명만 투입되면 된다.
  if (weakLen === 1) return 1;

  // 친구 배열의 순열을 구하는 함수
  function permutation(L, arr) {
    if (L === distLen) {
      for (let i = 0; i < weakLen; i++) {
        // 여기서 i는 처음 점검을 시작할 외벽의 인덱스다. [1, 5, 6, 10, 13, 17, 18,22] 에서 1,5,6,10까지만 조회한다.
        const end = i + weakLen; // 케이스마다, 외벽의 갯수만큼만 점검하면 완료되므로 end 변수에 넣었다.
        let left = i; // 점검을 시작할 외벽의 인덱스이다.
        let cnt = 0;

        for (let elem of arr) {
          if (left >= end) break; // left >= end의 경우는 외벽 점검이 끝났음을 의미한다. 더이상 반복문을 돌 필요가 없다.
          cnt += 1; // 친구가 특정 외벽에서 이동을 시작하므로, cnt를 올려준다.
          const maxDist = elem + flattenWeak[left]; // 친구가 이동할 수 있는 최대 위치를 나타낸다. 10에서 시작해서 4만큼 이동 가능하면 maxDist는 14일 것.

          while (left < end && maxDist >= flattenWeak[left]) {
            left++;
            // while문이 종료되는 조건을 생각해보자.
            // end에 도달했다면 이미 점검이 끝난 것이다.
            // maxDist가 left 인덱스보다 작다면, 현재의 elem(친구)는 left-1 까지만 방문한 셈이다.
            // 만약 두 조건을 만족한다면, 친구는 더 이동할 수 있으므로 left를 증가시켜준다.
          }
        }

        if (left < end) continue; // left가 end보다 작다는 것은, 모든 친구를 동원했음에도 외벽을 점검하지 못한 것이다.

        answer = Math.min(answer, cnt); // 매 케이스마다, 친구의 수 최솟값을 갱신시켜준다.
      }
      return;
    }

    for (let i = 0; i < distLen; i++) {
      // 순차적으로 조회해야하므로, 방문처리와 방문 후에는 미방문처리로 바꾼다.
      if (visits[i]) continue;
      visits[i] = 1;
      permutation(L + 1, [...arr, dist[i]]);
      visits[i] = 0;
    }
  }

  // 순열 함수를 실행한다.
  permutation(0, []);

  return answer === distLen + 1 ? -1 : answer;
}

사실 좀 고생했다.

TMI지만, 계속 테스트케이스 25개 중 10개에서 런타임 에러가 발생했었다.

 

그래서 로직이 잘못 된 것인지, 특이 케이스를 고려 못한것인지 계속 고민했었는데..
기존에 배열 answer에 모든 cnt 값을 추가해줬는데, answer를 문자로 바꾸고 최솟값을 비교하니 문제가 해결되었다..

 

(사실 이것 때문에 나처럼 고생하는 분이 있을 수도 있어서 오랜만에 정리하게 된 것이기도 하다.)

 

그다지 궁금하진 않겠지만, 혹시 궁금하실 분을 위해 코드는 밑에 첨부해두겠다.

 

 

런타임 에러를 유발한 코드

function solution(n, weak, dist) {
  const flattenWeak = [...weak, ...weak.map((elem) => elem + n)];
  const weakLen = weak.length;
  const distLen = dist.length;
  const visits = new Array(distLen).fill(0);
  const answer = [];

  if (weakLen === 1) return 1;

  function permutation(L, arr) {
    if (L === distLen) {
      for (let i = 0; i < weakLen; i++) {
        const end = i + weakLen;
        let left = i;
        let cnt = 0;

        for (let elem of arr) {
          if (left >= end) break;
          cnt += 1;
          const maxDist = elem + flattenWeak[left];

          while (left < end && maxDist >= flattenWeak[left]) {
            left++;
          }
        }

        if (left < end) continue;

        answer.push(cnt);
      }
      return;
    }

    for (let i = 0; i < distLen; i++) {
      if (visits[i]) continue;
      visits[i] = 1;
      permutation(L + 1, [...arr, dist[i]]);
      visits[i] = 0;
    }
  }

  permutation(0, []);

  return answer.length === 0 ? -1 : Math.min(...answer);
}