[프로그래머스] LV.3 외벽점검 (JS)

문제

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

레스토랑의 구조는 완전히 동그란 모양이고 외벽의 총 둘레는 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 해주세요.

입출력 예시

n	weak	dist	result
12	[1, 5, 6, 10]	[1, 2, 3, 4]	2
12	[1, 3, 4, 9, 10]	[3, 5, 7]	1

풀이

2020 카카오 블라인드 테스트에서 출제된 문제이다. 어떻게 접근해야 할 지 어느 정도 사고력을 요구하며, 생각의 전환 역시 필요한 문제이다. 따라서 접근 방향을 제대로 잡지 못하면 한없이 어려운 문제가 될 수 있다. 하나씩 차근차근 접근해보자.

취약 지점 접근 순서

입출력 예시에서 제시된 이미지를 보면 취약지점 weak가 주어졌을 때 이는 시계 혹은 반시계 방향으로 접근할 수 있다는 것을 알 수 있다. 때문에 주어진 취약지점에서 어느 위치에서 시작하느냐에 따라 시작점과 도착점이 달라지게 된다. 이때 우리는 어느 지점에서 시작하느냐에 따라 필요한 투입인원 수가 각각 달라지게 되므로, 최소 투입 인원을 찾기 위해서는 주어진 취약지점에서 모든 위치를 시작점으로 잡아서 검사해볼 필요가 있다.

이때 방향 자체는 크게 중요하지 않다. 시계방향이든 반시계방향이든 두 지점간의 거리 차이는 방향에 상관없이 일정하기 때문에, 두 지점간의 차이를 정확하게 구할 수 있다면 우리가 방향에 관해 일일이 개입할 필요는 없다. 즉 두 지점간의 차로 최소 투입 인원을 고려할 수 있다.

따라서 첫번째 예시에서 주어진 취약지점은 [1, 5, 6, 10] 이기 때문에 다음과 같이 4가지 투입 경로가 가능하다.

1. 1 -> 5 -> 6 -> 10
2. 5 -> 6 -> 10 -> 1
3. 6 -> 10 -> 1 -> 5
4. 10 -> 1 -> 5 -> 6

이 경우 주어진 외벽의 길이 n이 12이기 때문에 각 지점별 차이 계산에 주의해야 한다. 예를 들어 1과 10의 차이는 9이지만, 만약 역순으로 접근한다면 3이 된다. (시계를 생각하면 이해하기 쉽다: 10 -> 11 -> 12 -> 1) 최소 투입 인원을 고려하려면 이 차이가 최소가 되는 지점 위주로 계산해야 할 것이다. 그렇지만 위에 나열한 경로로 접근한다면 우리가 방향을 어디로 택하냐에 따라 거리가 달라지므로 그때마다 직접 조정해주어야 할 필요가 있다. 하지만 위에서 언급한 바와 같이 중요한 것은 방향보다 지점 간의 차이이다. 이 차이를 항상 최소값으로 유지하기 위해서는 방향을 하나로 고정하고 주어진 n값을 초과하는 경우엔 해당 값에 n을 더해주어 순차적인 접근을 하도록 구성해줄 수 있다. 즉 위의 투입 경로를 다음과 같이 수정 가능하다.

1. 1 -> 5 -> 6 -> 10
2. 5 -> 6 -> 10 -> 13
3. 6 -> 10 -> 13 -> 17
4. 10 -> 13 -> 17 -> 18

1번 경로의 경우는 시계 방향으로 순차적으로 접근할 시 n값을 초과하여 넘어가지 않으므로 그대로 유지할 수 있다. 2번 부터는 10번 이후의 순번은 주어진 n 값을 초과하여 접근한다. 따라서 12를 더해주어 순차적인 방향으로 접근하도록 해준다. 이 역시 시계를 생각하면 쉽다. 오전 11시에서 오후 1시로 넘어가는 것을 이와 같이 11과 1을 통해 나타낼 수도 있지만, 11시와 13시로 나타내는 것과 유사하다. 이처럼 경로를 순차적으로 바꾸면 각 지점간 최소 거리를 계산할 수 있다. 따라서 weak 배열이 주어졌을때, 이를 각 위치를 시작점으로 삼아 도착지점의 위치값을 포함하는 배열을 구현해주자. 즉 위 처럼 [1, 5, 6, 10]이 주어졌을때 [1, 5, 6, 10, 13, 17, 18]의 배열을 만들어야 한다.

const len = weak.length;
// 순차 접근 배열의 크기는 기존 weak 배열의 길이*2 - 1과 같다.
const linear_weak = new Array(len*2 - 1).fill(0);

// linear_weak 배열의 크기만큼 반복문을 돌면서
// 각 시작지점의 도착점을 계산하여 추가
for(let i = 0; i < len*2 - 1; i++)
  linear_weak[i] = i < len ? weak[i] : weak[i-len] + n;

순열

다음은 접근할 수 있는 인원의 순서를 고려해야 한다. 인원은 최대 8명으로 제한되어 있다. 각각의 인원이 접근할 수 있는 범위가 dist로 주어지는데 이 길이 최대값이 8이기 때문이다.

위에서 우리는 접근 방향을 시계 방향으로 순차적으로 만들어주었다. 그러나 순차적으로 접근한다 하더라도 투입되는 인원이 어디까지의 거리를 커버할 수 있는지에 따라 인원수가 달라질 수 있다. 따라서 우리는 주어진 dist를 가지고 모든 경우의 수를 구성해야 한다.

이때 이를 순열(permutaion)으로 경우의 수를 구해주어야 하는데, 만약 2명의 인원이 투입되고 각각 4와 1의 거리만큼 작업이 가능하다고 할 때, [1, 4]의 순서로 투입되느냐 또는 [4, 1]의 순서로 투입되느냐에 따라 똑같은 경로라고 할지라도 불가능한 경우가 발생할 수 있다. 따라서 조합이 아닌 순열로 경우의 수를 구해야한다. 최대값이 8이고 투입될 수 있는 인원은 1명부터 8명까지이므로 8P1 ~ 8P8까지의 경우의 수, 즉 8! 의 시간복잡도가 필요하기에 모든 순열을 구하는 것은 효율성을 초과하지 않는다.

자바스크립트는 다른 언어와 달리 순열을 구하는 내장 함수가 따로 없다. 때문에 직접 구현해주어야 한다. 이와 관련되어 조합과 순열을 자바스크립트로 구현하는 포스트를 참고하기 바란다. 순열은 다음과 같이 구현할 수 있다.

// n은 xPn 의 수식에서 n 의 역할이다.
// 해당 함수의 자세한 설명은 위 링크된 포스트에서 참고하자.
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(idx+1)];
    const perms = getPermutation(rest, n-1);
    const attached = perms.map(perm => [fixed, ...perm]);
    result.push(...attached);
  });
  
  return result;
}                   

최소 투입 인원 계산

순차 접근 배열과 순열 함수를 모두 구현했다면 이제 최소 투입 인원을 구할 수 있다. 먼저 최소의 인원이 투입되기 위해서는 당연히 가장 멀리 갈 수 있는 인원부터 투입시켜 봐야할 것이다. 때문에 주어진 dist 배열을 먼저 내림차순으로 정렬하자.

위에서 구해준 순열 함수를 통해 1명부터 8명이 투입되는 경우까지 모두 고려한 경우의 수를 구해주어야 한다. 그리고 각각의 경우의 수를 통해 위에서 구해준 순차 접근 경로를 모두 돌면서 해당 인원이 모든 취약 지점을 커버 가능한지 검사해주도록 하자. 그러기 위해서는 다음과 같이 생각할 수 있다.

1. weak 크기만큼 반복문을 돌면서, 각각의 경로를 추출
   • linear_weak.slice(j, len + j);
   • j는 0부터 weak.length-1 까지 반복
   • 따라서 ...slice(0, 4), ...slice(1, 5), ... 순으로 각 경로를 추출 가능
2. 각 경로의 첫 지점과 현재 투입 인원의 작업 범위를 더한 값이 해당 인원의 커버가능한 거리
   • 예를 들어 시작지점이 1이고, 지금 투입되는 인원의 거리가 4라면,
   • 해당 인원은 5 지점까지 작업 가능
   • 따라서 해당 값보다 작은 값은 모두 제거
   • 이를 인원 수 만큼 반복했을 때 모든 값이 제거 된다면 해당 인원으로 모든 취약지점 검토가 가능하다는 뜻

위 두가지의 경우를 신경써서 구현해주면 된다. 따라서 다음과 같이 코드를 작성할 수 있다.

dist.sort((a, b) => b-a);	// 내림차순 정렬

// 1부터 최대 8까지 반복하며 순열 탐색
for(let i = 1; i <= dist.length; i++) {
  const permutation = getPermutation(dist, i);
  
  // permu는 i 인원으로 접근 가능한 모든 경우의 수
  for(const permu of permutation) {
    for(let j = 0; j < len; j++) {
      // line은 순차적으로 접근 가능한 모든 경로
      let line = linear_weak.slice(j, len+j);
      // p는 permu 에서 각 인원의 작업 거리
      for(const p of permu) {
        // 경로 시작점과 현재 인원의 작업 거리를 더한 값이 범위
        const coverage = line[0] + p;
        // 이 범위보다 큰 값은 해당 인원이 작업 불가하므로
        // 큰 값만 남겨두어 갱신
        // 다음 반복문에서 현재 인원이 도달하지 못한 지점이
        // 경로 시작점으로 계산되어 다음 coverage 계산
        line = line.filter(e => e > coverage);
        // 경로를 다 작업하면 line의 길이는 0이 됨
        // 따라서 이 경우 현재 인원 i를 바로 return
        if(!line.length) return i;
      }
    }
  }
}

// 위에서 최소 인원을 찾지 못한 경우 -1 반환
return -1;

전체코드

순차적으로 접근을 해야한다는 생각을 떠올렸다면, 순열을 구해 비교적 쉽게 접근할 수 있었을 것 같다. 그렇지 않은 경우엔 각 방향에 따른 최소 거리 값을 상황에 맞게 조절해야 하기 때문에 다소 복잡한 구현이 되지 않았을까 싶다. 주석을 제외한 전체코드는 다음과 같다.

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://programmers.co.kr/learn/courses/30/lessons/60062