[프로그래머스/Level2] 외벽 점검 (JAVA)

📖 문제

프로그래머스

 

 

 

 

💡  풀이 방식

원형 완전탐색 + 순열

 

1. 모든 weak 케이스 만들기

: 다음 시작 지점 기준으로 마지막 weak point + N까지 직선으로 펼치기 (원형 큐 방식)

// 모든 weak 케이스 만드는 메서드 (완탐. 원형 큐처럼 펼치기) - 1 5 6 10 / 5 6 10 13 / 6 10 13 17 / 10 13 17 18
private static void makeWeakCases() {
    int[] wc = weak.clone();
    weakCases[0] = wc.clone();

    for(int i = 1 ; i < weak.length ; i++) {
        int tmp = wc[0];

        for(int j = 1 ; j < weak.length ; j++) {
            wc[j - 1] = wc[j];
        }

        wc[weak.length - 1] = tmp + n;	// 직선으로 펼치기
        weakCases[i] = wc.clone();
    }
}

예를 들어, N = 12, weak = [1, 5, 6, 10]인 경우 처음에 위치 1을 기준으로 직선으로 펼쳤다면, 이번에는 위치 5를 기준으로 [5, 6, 10, 13]과 같이 직선 형태로 만들어 주면 됩니다. 이때, 13은 값이 증가하는 형태로 만들어 주기 위해 1 + 12를 해준 결과입니다.

- 출처 : https://tech.kakao.com/2019/10/02/kakao-blind-recruitment-2020-round1/

 

 

2. 모든 dist 케이스 만들기

: dist에서 점검할 친구 1명 ~ 8명까지 순열로 선택해 나열하는 방법을 모두 고려한다. 

// 친구로 모든 dist 케이스 만드는 메서드 (순열) - 3 5 7 / 3 7 5 / 5 3 7 ...
private static void makeDistCases(int depth) {
    if(depth == dist.length) {
        for(int[] wc : weakCases)   // 3. 모든 weak 케이스에 대해 모든 dist 케이스 검사
            chk(dist_case, wc);
        return;
    }

    for(int i = 0 ; i < dist.length ; i++) {
        if(!visited[i]) {
            visited[i] = true;
            dist_case[depth] = dist[i];

            makeDistCases(depth + 1);

            //dist_case[depth] = 0;
            visited[i] = false;
        }
    }
}

 

 

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

: 구한 순서대로 weak point를 최대로 할당해, 전체 weak point를 커버 가능하지 검사한다.

// 모든 weak 케이스에 대해 모든 dist 케이스 검사하는 메서드
private static void chk(int[] dc, int[] wc) {
    int now = 0;
    int idx = 0;

    while(now < wc.length && idx < dc.length) { // 기존 weak 길이만큼 탐색
        int next = now + 1;

        // 순서대로 외벽을 얼만큼 점검할 수 있는지 확인
        while(next < wc.length && wc[now] + dc[idx] >= wc[next]) {
            next++;
        }

        now = next;
        idx++;
    }

    if(now == wc.length && idx < answer)    // 모든 외벽 점검했는지 확인
        answer = idx;
}

 

 

 

🔺 코드

import java.util.*;
 
class Solution {    
    static int n;
    static int[] weak, dist;
    static int[][] weakCases;
    
    // dfs용
    static boolean[] visited;
    static int[] dist_case;
    
    static int answer = Integer.MAX_VALUE;
    
    public int solution(int n, int[] weak, int[] dist) {
        this.n = n;
        this.weak = weak;
        this.dist = dist;
        
        weakCases = new int[weak.length][weak.length];
        makeWeakCases();    // 1. 모든 weak 케이스 만들기
        
        visited = new boolean[dist.length];
        dist_case = new int[dist.length];   // 순열 저장할 배열
        makeDistCases(0);
 
        return (answer == Integer.MAX_VALUE) ? -1 : answer;
    }
    
    // 1. 모든 weak 케이스 만드는 메서드 (완탐. 원형 큐처럼 펼치기) - 1 5 6 10 / 5 6 10 13 / 6 10 13 17 / 10 13 17 18
    private static void makeWeakCases() {
        int[] wc = weak.clone();
        weakCases[0] = wc.clone();
        
        for(int i = 1 ; i < weak.length ; i++) {
            int tmp = wc[0];
            
            for(int j = 1 ; j < weak.length ; j++) {
                wc[j - 1] = wc[j];
            }
            
            wc[weak.length - 1] = tmp + n;
            weakCases[i] = wc.clone();
        }
    }
    
    // 2. 모든 dist 케이스 만드는 메서드 (순열) - 3 5 7 / 3 7 5 / 5 3 7 ...
    private static void makeDistCases(int depth) {
        if(depth == dist.length) {
            for(int[] wc : weakCases)   // 3. 모든 weak 케이스에 대해 모든 dist 케이스 검사
                chk(dist_case, wc);
            return;
        }
        
        for(int i = 0 ; i < dist.length ; i++) {
            if(!visited[i]) {
                visited[i] = true;
                dist_case[depth] = dist[i];
                
                makeDistCases(depth + 1);
                
                dist_case[depth] = 0;
                visited[i] = false;
            }
        }
    }
    
    // 3. 모든 weak 케이스에 대해 모든 dist 케이스 검사하는 메서드
    private static void chk(int[] dc, int[] wc) {
        int now = 0;
        int idx = 0;
        
        while(now < wc.length && idx < dc.length) { // 기존 weak 길이만큼 탐색
            int next = now + 1;
            
            // 순서대로 외벽을 얼만큼 점검할 수 있는지 확인
            while(next < wc.length && wc[now] + dc[idx] >= wc[next]) {
                next++;
            }
            
            now = next;
            idx++;
        }
        
        if(now == wc.length && idx < answer)    // 모든 외벽 점검했는지 확인
            answer = idx;
    }
}

 

 

➕ 다른 풀이 방식

- 3번 과정이 약간 다르다.

[java] 프로그래머스 (외벽 점검) Level 3

 

프로그래머스 외벽 점검 java

 

 

- dist 배열을 오름차순 정렬하고, 뒤에서부터 0까지 DFS 진행! (내가 생각했던 부분)

[프로그래머스/자바] 외벽 점검 풀이 - 2020 KAKAO BLIND RECRUITMENT

---

💦 어려웠던 점

아따 다 어렵다,,,,,,,,,ㅎㅎ

 

 

🧐 새로 알게 된 내용

- 원형 탐색 위해 배열을 확장해서 붙이는 방법. 이러면 반시계 방향까지 커버한다고 한다.

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[프로그래머스] 2020 카카오 #6 외벽 점검 (Java)

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

 

[프로그래머스] 2020 KAKAO BLIND RECRUITMENT 외벽 점검 (Java)

 

외벽점검 - JAVA