(javascript) 외벽 점검

https://school.programmers.co.kr/learn/courses/30/lessons/60062?language=javascript

프로그래머스

 

오랜만에 코딩 문제를 풀었다.

 

 길이가 n인 원형 리스트로 주어진 외벽에서 최대 10군데의 약점이 주어진다. 한번에 d만큼의 길이를 커버할 수 있는 친구들의 목록 dist가 주어질 때, 친구들을 최소한으로 사용해서 모든 약점을 커버해야한다.

 

 기본적으로 백트래킹 방식으로 풀 수 있다고 판단했다.

 주어진 n, weak, dist에서 한명의 친구를 배치하는 백트래킹 함수 foo를 정의한다. foo는 dist에서 친구를 한명 선택해서 배치하고, 변화한 상태를 넘겨서 foo를 재귀호출한다. 가능한 모든 경우의 수를 확인한 수, 사용한 친구의 수가 최소인 경우를 반환한다.

 외벽의 전체 길이가 n, 약점의 수가 최대 15, 친구들의 수가 최대 8이므로 최악의 경우 모든 경우의 수를 탐색한다고 해도 15 * 8! 가지의 경우가 나온다.

 

 핵심 아이디어는 원형 리스트인 외벽을 펼쳐서 선형으로 만드는 것이다. 원형 리스트를 두 바퀴 순회하면 선형 리스트로 만들 수 있다.

 코드의 linear_weak가 바로 외벽을 선형 배열로 만든 것이다.

 외벽을 선형 배열로 만들면 모듈러 연산같은걸로 머리를 복잡하게 만들 필요가 없어서 편하다.

 

 foo는 최초에 호출을 시작한 위치 originIdx, 현재 탐색을 시작할 위치 startidx, 현재까지 사용한 친구의 수 count, 친구를 사용했는지 확인하는 배열 visited를 매개변수로 받는다.

 foo의 기저 조건은 첫번째, count가 dist.length보다 큰 경우이다. 이 경우는 더이상 사용 가능한 친구가 남아있지 않은 경우이다. -dist.length + 1을 반환한다.

 두번째는 startIdx >= originIdx + weakLen인 경우이다. 최초 탐색 위치로부터 weakLen만큼 지난 위치를 탐색한다는 말은 한바퀴를 모두 돌았다는 뜻이므로, 모든 약점을 커버했다고 볼 수 있다. 이 경우 현재 count를 반환한다.

 

 기저 조건을 만족하지 못했다면 현재 탐색 위치에 친구를 한명씩 배치해본다. 현재 배치 가능한 친구들 중에 사용 가능한 친구가 있다면 친구를 배치한다. 그리고 해당 친구를 사용했다고 표시해준다.

 변화한 상태를 가지고 foo를 재귀호출한다. originIdx는 변하지 않는 값이므로 그대로 전달해준다. 다음 탐색할 위치 nextIdx를 계산해준다. count에 1을 더해서 전달한다. visited는 참조 변수이므로 그대로 전달해준다.

 재귀 호출을 했다면 상태를 다시 되돌려준다. visited밖에 되돌려줄 상태가 없긴 하다.

 

 모든 친구들을 한번씩 배치해봤다면 그 중 가장 적은 수의 친구를 배치한 경우를 찾는다. 그리고 그 값을 반환해준다.

 

코드

 

function solution(n, weak, dist) {
    const weakLen = weak.length;
    let answer = dist.length + 1;

    const linear_weak = new Array(weakLen * 2).fill(0);
    for (let i = 0; i < weakLen; i++) {
        linear_weak[i] = weak[i];
        linear_weak[i + weakLen] = weak[i] + n;
    }

    function foo(originIdx, startIdx, count, visited) {
        if (count > dist.length) {
            return -1;
        }
        if (startIdx >= originIdx + weakLen) {
            // 모든 약점 커버함
            return count;
        }
        var min = dist.length + 1;
        for (var j = 0; j < dist.length; j++) {
            if (!visited[j]) {
                // 점검
                var startPos = linear_weak[startIdx];
                var endPos = startPos + dist[j];
                var nextIdx = startIdx;
                while (linear_weak[nextIdx] <= endPos) {
                    nextIdx++;
                }
                visited[j] = true;
                // 재귀
                var result = foo(originIdx, nextIdx, count + 1, visited);
                if (result < min) min = result;
                // 복원
                visited[j] = false;
            }
        }
        return min;
    }

    for (var i = 0; i < weakLen; i++) {
        var result = foo(i, i, 0, new Array(dist.length).fill(false));
        if (result < answer) answer = result;
    }

    if (answer > dist.length) return -1;
    return answer;
}

 

후기

 외벽이 원형 배열로 주어져서 한참 고민했다. 이 인덱스가 weak.length를 넘기면... pos가 n을 넘기면... 머리아프게 이러저러 처리를 하면서 계속 틀려서 고민중에 원형 배열을 선형 배열로 바꾸는 힌트를 찾았다. 그리고 바로 통과해버렸다.