외벽점검 - JAVA

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

프로그래머스

---

이 문제는 어려워서 다른 분의 풀이를 참고했읍니다..😭

 

이 문제의 핵심 키워드는 완전 탐색과 순열이다

완전 탐색은 n, weak, dis 모두 최대값의 개수가 적기 때문에 완전 탐색을 통해 정답을 얻기 떄문에 사용된다

순열은 weak와 dist 모두 가능한 모든 경우의 수를 만들어야 하기 때문에 순열로 모든 케이스를 따지기 위해 사용된다

 

문제 풀이 방식은 다음과 같다

 

1. 모든 weak 케이스 만들기

예를 들어 [1, 5, 6, 10]의 weak 케이스에 경우, weak에서 만들 수 있는 모든 케이스는 [1,5,6,10], [5,6,10,13], [6,10,13,17], [10,13,17,18] 가 된다

이는 원형 큐의 방식처럼 만들어 주는 것이다

어차피 문제에서 weak 길이의 최대를 15로 했기 때문에 모든 테스트 케이스를 만들어도 최대 15개이기 떄문에 완전 탐색으로 진행해도 무리가 없다따라서 모든 테스트 케이스를 만들어주면, 한 방향으로만 탐색을 계속 진행해도 모든 경우를 다 탐색할 수 있다

 

2. 모든 dist 케이스 만들기

완전 탐색을 하기 위해, 순열을 통해 모든 dist 케이스를 만들어준다

예를 들어 [3, 5, 7]의 dist인 경우, [3,5,7], [3,7,5], [5,3,7], [5,7,3], [7,5,3], [7,3,5] 의 모든 케이스를 만들 수 있다

 

3. 모든 weak 케이스에 대해 모든 dist 케이스로 검사하기

이제 위에서 만든 케이스들로, 모든 weak 케이스에 대해 모든 dist 케이스를 검사한다

반복문을 통해 weak 케이스의 시작점부터 dist 켕스의 값을 하나씩 가져오면서 검사가 되는 weak 지점을 모두 패스한다

예를 들어, [1 3, 4, 9, 10]의 weak와 [3, 5, 7]의 dist를 이용하여 탐색한다고 가정하자

• 1번 지점에서 3짜리 dist가 사용된다
• 1+3=4 이므로, 3, 4번 지점은 1번과 함께 체크가 가능하다
• 그럼 다음 출발지는 9번 지점이 되고, 여기서 5짜리 dist를 사용한다
• 그럼 9+5=14이기 때문에 10번 지점까지 한번에 체크가 가능하다
• 따라서 2개의 dist 값만 사용하여 모두 탐색이 진행된 것이다

 

이런 식으로 가장 적은 dist를 사용하여 모든 경우를 탐색한 값을 return 해주면 된다

 

 

 

자바 코드)

package programmers;

import org.junit.Assert;
import org.junit.Test;


public class WallCheck {
    int[] weak, dist;
    int[][] weak_cases;
    int n, answer;
    public int solution(int n, int[] weak, int[] dist) {
        weak_cases = new int[weak.length][weak.length];
        this.weak = weak;
        this.dist = dist;
        this.answer = dist.length+1;
        this.n = n;

        makeWeakCases();
        makeDistCases(new boolean[dist.length], new int[dist.length], 0);
        if(answer == dist.length+1)
            return -1;
        else
            return answer;
    }

    void makeWeakCases(){
        int[] weak_case = this.weak.clone();
        weak_cases[0] = weak_case.clone();
        for(int i = 1; i < weak.length; i++){
            int temp = weak_case[0];
            for(int j = 1; j < weak.length; j++){
                weak_case[j-1] = weak_case[j];
            }
            weak_case[weak.length-1] = temp+n;
            weak_cases[i] = weak_case.clone();
        }
    }

    void makeDistCases(boolean[] dist_visit, int[] dist_case, int idx){
        if(idx == dist.length){
            for(int[] weak_case: weak_cases)
                check(dist_case, weak_case);
        }
        for(int i = 0; i < dist.length; i++){
            if(!dist_visit[i]){
                dist_visit[i] = true;
                dist_case[idx] = dist[i];
                makeDistCases(dist_visit, dist_case, idx+1);
                dist_case[idx] = 0;
                dist_visit[i] = false;
            }
        }
    }

    void check(int[] dist_case, int[] weak_case){
        int cur = 0, next;
        int dist_idx = 0;
        while(cur < weak_case.length && dist_idx < dist_case.length){
            next = cur+1;
            while(next < weak_case.length &&
                    weak_case[cur] + dist_case[dist_idx] >= weak_case[next]){
                next++;
            }
            cur = next;
            dist_idx++;
        }

        if(cur == weak_case.length && dist_idx < answer)
            answer = dist_idx;
    }
    @Test
    public void test() {
        Assert.assertEquals(2, solution(12, new int[]{1, 5, 6, 10}, new int[]{1, 2, 3, 4}));
        Assert.assertEquals(1, solution(12, new int[]{1, 3, 4, 9, 10}, new int[]{3, 5, 7}));
        Assert.assertEquals(2, solution(200, new int[]{0, 100}, new int[]{1, 1}));
        Assert.assertEquals(3, solution(200, new int[]{0, 10, 50, 80, 120, 160}, new int[]{1, 10, 5, 40, 30}));
        Assert.assertEquals(1, solution(12, new int[]{0, 10}, new int[]{1, 2}));
        Assert.assertEquals(1, solution(12, new int[]{4}, new int[]{1, 2}));
        Assert.assertEquals(2, solution(30, new int[]{0, 3, 11, 21}, new int[]{10, 4}));
        Assert.assertEquals(-1, solution(200, new int[]{1, 3, 5, 7, 9, 11}, new int[]{1, 1, 1, 1, 1}));
        Assert.assertEquals(1, solution(19, new int[]{0, 10}, new int[]{9}));
    }
}

 

---

[참고]

https://dev-note-97.tistory.com/241

[프로그래머스] 외벽 점검 / Java