[Algorithm] 외벽점검

📋 문제

레스토랑을 운영하고 있는 "스카피"는 레스토랑 내부가 너무 낡아 친구들과 함께 직접 리모델링 하기로 했습니다. 레스토랑이 있는 곳은 스노우타운으로 매우 추운 지역이어서 내부 공사를 하는 도중에 주기적으로 외벽의 상태를 점검해야 할 필요가 있습니다.

레스토랑의 구조는 완전히 동그란 모양이고 외벽의 총 둘레는 n미터이며, 외벽의 몇몇 지점은 추위가 심할 경우 손상될 수도 있는 취약한 지점들이 있습니다. 따라서 내부 공사 도중에도 외벽의 취약 지점들이 손상되지 않았는 지, 주기적으로 친구들을 보내서 점검을 하기로 했습니다. 다만, 빠른 공사 진행을 위해 점검 시간을 1시간으로 제한했습니다. 친구들이 1시간 동안 이동할 수 있는 거리는 제각각이기 때문에, 최소한의 친구들을 투입해 취약 지점을 점검하고 나머지 친구들은 내부 공사를 돕도록 하려고 합니다. 편의 상 레스토랑의 정북 방향 지점을 0으로 나타내며, 취약 지점의 위치는 정북 방향 지점으로부터 시계 방향으로 떨어진 거리로 나타냅니다. 또, 친구들은 출발 지점부터 시계, 혹은 반시계 방향으로 외벽을 따라서만 이동합니다.

외벽의 길이 n, 취약 지점의 위치가 담긴 배열 weak, 각 친구가 1시간 동안 이동할 수 있는 거리가 담긴 배열 dist가 매개변수로 주어질 때, 취약 지점을 점검하기 위해 보내야 하는 친구 수의 최소값을 return 하도록 solution 함수를 완성해주세요.

 

제한사항

• n은 1 이상 200 이하인 자연수입니다.
• weak의 길이는 1 이상 15 이하입니다.
  
  • 서로 다른 두 취약점의 위치가 같은 경우는 주어지지 않습니다.
  • 취약 지점의 위치는 오름차순으로 정렬되어 주어집니다.
  • weak의 원소는 0 이상 n - 1 이하인 정수입니다.
• dist의 길이는 1 이상 8 이하입니다.
  
  • dist의 원소는 1 이상 100 이하인 자연수입니다.
• 친구들을 모두 투입해도 취약 지점을 전부 점검할 수 없는 경우에는 -1을 return 해주세요.

 

입출력 예

12	[1, 5, 6, 10]	[1, 2, 3, 4]	2
12	[1, 3, 4, 9, 10]	[3, 5, 7]	1

 

✏️ 풀이

문제에 대한 접근이 꽤 어려웠다. 모든 경우를 계산하면 시간초과가 날 것 같아서 고민을 많이 했는데 우선 시도해보기로 했다.

 

외벽은 둥근 형태로 되어 있어 계산하기가 어려웠기 때문에 편하게 계산하기 위해서 일자로 펴주는 작업을 했다. 시계를 예로 든다면 다음과 같은 작업을 했다. 1시 지점을 인덱스 0, 12시가 인덱스 11이라고 가정했을 때 일자로 펴서 나열한다면 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]가 된다. 하지만 문제는 둥근 형태이기 때문에 1시 위치(인덱스 0)에서 12시 위치(인덱스 11)으로도 접근이 가능해야 한다. 그래서 배열을 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] 이런식으로 추가적인 요소를 넣어줬다. 하지만 계산할 때를 생각해본다면 12시 위치에서 1시 위치로 이동할 때 12 - 1 또는 1 - 12를 하더라도 1이라는 숫자가 나오지 않는다. 따라서 둘래(n)만큼 더해서 넣어 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24]의 배열로 변환시켜줬다.

 

취약점을 이동할 때 한명의 친구가 갈 수 있는 거리도 고려해야 하기 때문에 순서가 중요했다. 따라서 모든 경우의 수를 구하기 위해 combiDist 라는 함수를 만들었다. 이 함수는 결과 배열(dists), 뽑을 친구(cnt), 현재의 조합을 가지는 배열(arr), 뽑은 친구를 확인하기 위한 배열(check) 총 네개의 인자를 받아 이차원 배열으로 친구들의 순서 조합을 반환한다.

 

이제 모든 경우를 탐색할텐데 시작위치에 따라서도 결과가 변할 수 있기 때문에 반복문으로 0부터 취약점의 길이만큼 반복하도록 했다. 위에서 예시들었던 시계를 기준으로 한다면 1시부터 12시 위치까지 탐색한다.

 

두 번째 반복문으로 몇 명의 친구들을 조합할지 계산하기 위해 cnt라는 변수를 가지고 반목문을 돌려줬다. 이때 최소 한명의 친구는 필요하기 때문에 1부터 친구들의 수까지 반복했다. 이 반복문 내부에서 친구들의 순서 조합(dists)을 구하고 순회하며 확인한다.

 

확인할 때는 현재 취약 지점에서 원래의 취약점 개수를 더한 지점까지를 순회한다. 만약 취약점을 다 돌지 못했지만 남은 친구가 없는 경우 반복문 종료한다. 다 돌 수 있는지를 확인하기 위한 조건문이 있는데 이는 현재 돌고 있는 친구가 현재 취약 지점에서 다음 취약 지점으로 갈 수 있는지를 확인하고 갈 수 있다면 친구가 갈 수 있는 남은 거리를 갱신(취약 지점 사이의 거리를 빼줌)하고, 갈 수 없다면 현재 배열에서 pop해주며 제거했다. 취약점을 모두 순회했음에도 남은 친구가 존재하거나, 현재 갈 수 있는 친구가 있는 경우, 또는 모든 취약점을 돌고 마지막 취약점에서 나온 경우(갈 수 있는 거리가 0이 된 경우) answer를 Math.min을 사용하여 갱신해준다.

 

마지막에 취약지점보다 answer가 큰 경우(처음에 answer를 Infinity로 초기화했음) 취약점을 돌 수 없다는 의미이기 때문에 -1을 반환했다.

 

문제는 해결했지만 시간이 꽤 오래 걸리는 것 같아서 시간을 줄일 방법을 생각했다. 그 중 하나가 cnt를 다루는 반복문(2번째 for문)에서 만약 현재의 answer보다 cnt가 같거나 크다면 확인할 의미가 없으므로 break하는 조건문을 하나 추가했다. 1000ms를 넘기는 케이스도 여럿 존재했는데 모두 1000ms 이하로 떨어지는 효과를 볼 수 있었다. 추가로 각 cnt마다 친구 순서 조합을 계속 구할 필요가 없으므로 cache하는 객체를 생성하려고 했는데 이 조합에서 pop하거나 수를 빼고 더하는 등 조작하기 때문에 깊은복사가 필요했고 오히려 더 많은 리소스를 사용할 것 같아 건드리지 않았다. 이 부분도 해결하면 더 효율성있는 코드가 될 것 같다!

 

⌨️ 코드

function solution(n, weak, dist) {
  var answer = Infinity;
  const weakLen = weak.length;
  const distLen = dist.length;

  for (let i = 0; i < weakLen; i++) weak.push(weak[i] + n);

  const combiDist = (dists, cnt, arr, check) => {
    if (cnt === arr.length) dists.push(arr);
    else {
      for (let i = 0; i < distLen; i++) {
        if (check[i]) continue;
        check[i] = 1;
        combiDist(dists, cnt, [...arr, dist[i]], [...check]);
        check[i] = 0;
      }
    }

    return dists;
  };

  for (let i = 0; i < weakLen; i++) {
    for (let cnt = 1; cnt < distLen + 1; cnt++) {
      if (answer <= cnt) break;

      const check = new Array(distLen).fill(0);
      const dists = combiDist([], cnt, [], check);

      for (const d of dists) {
        for (let k = i; k < i + weakLen - 1; k++) {
          if (!d.length) break;

          if (d[d.length - 1] >= weak[k + 1] - weak[k]) d[d.length - 1] -= weak[k + 1] - weak[k];
          else d.pop();
        }

        if (d.length) {
          answer = Math.min(answer, cnt);
          break;
        }
      }
    }
  }

  return answer > distLen ? -1 : answer;
}