[Programmers] 외벽 점검

문제

 

2020 KAKAO BLIND RECRUITMENT > 외벽 점검

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

 

 

아이디어

 

이 문제를 풀기 위해 가장 중요하게 생각해야 될 것은 스카피의 친구들인 dist들의 배치 방식입니다.

 

처음 문제를 접했을 땐 그리디, 동적프로그래밍을 이용해야 되나? 라고 생각했지만 결국엔 순열로 dist들을 배치하여 풀었습니다.

 

dist의 길이는 1이상 8이하이기 때문에 dist들의 순열을 구해도 문제될 것은 없었고 외벽을 점검할 dist의 순서, 탐색 시작 weak, 탐색 방향을 활용하였더니 문제를 풀 수 있었습니다.

 

코드를 구현하기 위해 생각했던 제가 생각한 아이디어는 다음과 같습니다.

 

1. dist 순열 구하기

2. 탐색 방향 정하기(시계, 반시계)

3. weak를 탐색하며 점검 시작 위치 정하기

4. 시작 위치를 기준으로 배열을 벗어나는 경우를 생각하여 새로운 weak 구하기, 예를 들어 예제 1번에서 점검 시작 위치는 6, 방향은 시계 방향으로 한 바퀴를 돈다면 (6, 10, 1, 5)순서로 방문하는데 인덱스 값을 나누지 않기 위해 (6, 10, 1+12, 5+12)로 새로운 weak를 생성

5. dist를 탐색하며 각각의 dist가 점검할 수 있는 최대 위치까지 점검하기

6. 모든 weak를 탐색할 때 까지 3~5를 반복

7. 모든 방향을 탐색할 때 까지 2~6을 반복

 

 

구현 코드 (JavaScript)

 

let res = Number.MAX_VALUE;

const makeP = (n, weak, dist, index) => { // 순열
    if(index >= dist.length) {

        // 시계방향
        for(let i=0; i<weak.length; i++) {
            const addWeak = []; // 인덱스를 나누지 않기 위해 0<=i<j에 해당하는 값에 +n 해주기
            for(let j=0; j<weak.length; j++) {
                if(j < i) {
                    addWeak.push(weak[j] + n);
                } else {
                    addWeak.push(weak[j]);
                }
            }

            let weakIndex = i; // 점검 시작 위치
            let weakCount = 0; // 점검된 weak 갯수
            for(let j=0; j<dist.length; j++) {
                let maxIndex = addWeak[weakIndex] + dist[j]; // 현재 dist가 점검할 수 있는 최대 위치

                while(addWeak[weakIndex] <= maxIndex && weakCount < weak.length) { // 최대 위치안에 들어있는 모든 weak를 점검
                    weakIndex = (weakIndex+1)%weak.length;
                    weakCount++;
                }

                if(weakCount >= weak.length) { // 모든 weak를 점검했을 경우
                    res = Math.min(res, j+1);
                }
            }
        }

        // 반시계 방향
        for(let i=0; i<weak.length; i++) {
            const addWeak = []; // 인덱스를 나누지 않기 위해 j<i<n에 해당하는 값에 +n 해주기
            for(let j=0; j<weak.length; j++) {
                if(j > i) {
                    addWeak.push(weak[j] - n);
                } else {
                    addWeak.push(weak[j]);
                }
            }

            let weakIndex = i; // 점검 시작 위치
            let weakCount = 0; // 점검된 weak 갯수
            for(let j=0; j<dist.length; j++) {
                let maxIndex = addWeak[weakIndex] - dist[j]; // 현재 dist가 점검할 수 있는 최대 위치

                while(addWeak[weakIndex] >= maxIndex && weakCount < weak.length) { // 최대 위치안에 들어있는 모든 weak를 점검
                    weakIndex = (weakIndex-1+weak.length)%weak.length;
                    weakCount++;
                }

                if(weakCount >= weak.length) { // 모든 weak를 점검했을 경우
                    res = Math.min(res, j+1);
                }
            }
        }

        return;
    }

    for(let i=index; i<dist.length; i++) {
        let temp = dist[index];
        dist[index] = dist[i];
        dist[i] = temp;

        makeP(n, weak, dist, index+1);

        temp = dist[index];
        dist[index] = dist[i];
        dist[i] = temp;
    }
}

function solution(n, weak, dist) {
    makeP(n, weak, dist, 0);

    return res === Number.MAX_VALUE ? -1 : res;
}

 

 

읽어주셔서 감사합니다.